Among beakers and test tubes, two chemists are about to welcome their newborns.

Everything is ready. Except the names.

Each name must use chemical symbols. If it can’t be broken down, it doesn’t pass.

Liam qualifies. Li (lithium) and Am (americium) are elements:

Nora is also elemental. It can be formed using N (nitrogen), O (oxygen), Ra (radium):

Emma doesn’t work. E is not an element, Em is also not an element, so there is no way to break it down.

They can’t keep checking names by hand. They need an automated way to spot elemental names. They need an algorithm!

First Try: One Element at a Time

My first thought was: this is trivial. We just scan the name, letter by letter. For each letter, we check if it matches an element in the periodic table.

For example, let’s try the name “Coco”:

That seems to work. Let us try another one: “Whisky”.

Yes, it sounds more like a pet name… but it is actually a real name.

So far, everything looks easy. But then we hit a problem.

Take a name like “Erica”.

If we only take one letter at a time, there is no element with symbol E. No R. No A. Can we say for sure that “Erica” is not elemental?

You can try any name you want in the box below and explore step by step how it attempts to form it with periodic table symbols one character at a time:

Two-Letter Elements

Let’s look closer. The periodic table does not only have one-letter symbols. There are 14 single-letter elements and 104 two-letter elements. None with three or more, that’s also an important detail.

If we look closely, we find Er (erbium) and Ca (calcium). These two elements, along with iodine (I), allow us to form “Erica”.

So now we know “Erica” is elemental. But how do we validate this in a systematic way?

Let’s try a simple strategy: scan from left to right.

1. Try the first letter “E”. It does not exist.
2. So we try two letters “Er”. That works (Erbium). We move forward. Now we have “ica”.
3. Try “i”. Works (Iodine). We move forward. Now we have “ca”.
4. Try “c”. Works (Carbon). We move forward. Now we have “a”.
5. “a” does not exist. And “a_” (two letters) is not possible either.

So this path fails. If we stop here, we conclude that “Erica” does not work. But that conclusion is wrong.

The mistake happened earlier. When we matched “c”, we had another valid option. Instead of taking “c”, we could have taken “ca” (Calcium). And that would have finished the name successfully.

The question is not whether we take one or two letters. We need to try both. If we commit too early to one option and never go back, we can miss a valid solution.

The Recursive Algorithm

Every time we try to form a name, there is a decision to make: Do we use one letter or two? This repeats again and again.

Since there are several possible paths, we must explore them all. Just in case we miss a valid form.

We could imagine this process as a decision tree: from the beginning, we try to build the name symbol by symbol, taking one or two characters at a time.

Let’s see them visually, with “Erica” as an example. At the start, we have two options: take E or take Er. The E path ends quickly. There is no element starting with E. But if we take Er, we move forward, because Erbium (Er) is indeed an element.

Now the problem reduces to forming “ica”. No matter what letters we took before, we just have to solve “ica”, repeating the process.

The I is iodine. Ic does not exist as an element. Again, the problem reduces to “ca”. We have two options: C and Ca. If we take C (Carbon), we are left with only “a”. But there is no element starting with A. That path ends here. If we take Ca (Calcium), there are no more letters left. We have reached the end. So yes, the name “Erica” is elemental.

In summary, we have explored all possibilities and, at least one allows us to form “Erica”.

Implementation

Let’s write this in Python.

First of all, we need all element symbols in lowercase. In Python, it is most convenient to use a set: this way we can quickly check if a string is a valid element.

ELEMENTS = {
    'h', 'he', 'li', 'be', 'b', 'c', 'n', 'o', 'f', 'ne', ...
}

Now, let’s translate our decision tree into code. Imagine a function called is_elemental that tells us if a name can be formed using only periodic table symbols.

This function receives a name and returns True if it is elemental, or False if it is not.

def is_elemental(name: str) -> bool:

Let’s start with the simplest case: if the name is empty, it means we have managed to form the whole name with elements. So we return True.

if name == "":
    return True

Now, we try the first branch of the tree: Can we take the first letter as an element? If so, we try to solve the rest of the name, removing that letter. If it works, we return True.

if name[:1] in ELEMENTS and is_elemental(name[1:]):
    return True

If not, we try the other branch: Can we take the first two letters as a valid symbol? If so, we try to solve the rest of the name, removing those two letters. If it works, we return True.

if len(name) >= 2 and name[:2] in ELEMENTS and is_elemental(name[2:]):
    return True

And if neither of these options works, then there is no way to form the name with elements. We return False.

Thus, each call to the function represents a fork in our decision tree. We try all possibilities until we find one that works… or run out of options.

The full code looks like this:

ELEMENTS = {
    'h','he',
    'li','be','b','c','n','o','f','ne',
    'na','mg','al','si','p','s','cl','ar',
    'k','ca','sc','ti','v','cr','mn','fe','co','ni','cu','zn','ga','ge','as','se','br','kr',
    'rb','sr','y','zr','nb','mo','tc','ru','rh','pd','ag','cd','in','sn','sb','te','i','xe',
    'cs','ba','la','ce','pr','nd','pm','sm','eu','gd','tb','dy','ho','er','tm','yb','lu',
    'hf','ta','w','re','os','ir','pt','au','hg','tl','pb','bi','po','at','rn',
    'fr','ra','ac','th','pa','u','np','pu','am','cm','bk','cf','es','fm','md','no','lr',
    'rf','db','sg','bh','hs','mt','ds','rg','cn','fl','lv','ts','og'
}

def is_elemental(name: str) -> bool:
    name = name.lower()
    if name == "":
        return True

    if name[:1] in ELEMENTS and is_elemental(name[1:]):
        return True

    if len(name) >= 2 and name[:2] in ELEMENTS and is_elemental(name[2:]):
        return True

    return False

Problems with Recursion

Before looking at more trees, let’s look at runtime.

With short names, this recursive solution looks very fast: usually just a few milliseconds, even in Python running in the browser (which is typically slower than local Python).

Try it yourself in the box below. Copy and paste these examples and compare execution times:

• Cocococococococococococococococococo
• Cocococococococococococococococococoa
• Cocococococococococococococococococa

Notice what happens: changing only the ending can change runtime dramatically.

Let’s follow exactly what is happening:

• Repeating coco many times can still be fast.
• Add just one final a (...cocoa) and runtime explodes.
• Remove one o so it ends in ca (...coca) and it becomes fast again.

So the issue is not simply length.

The recursive algorithm explores one branch at a time and can stop early if it finds a valid solution quickly. If no valid decomposition exists, it may need to explore almost the whole decision tree before returning False.

Now we can visualize the branching with “Coco”, where both Co and C + O are valid at many steps:

When a valid path is found quickly, recursion stops early. But in names like ...cocoa, many branches look promising until very late, so the algorithm does much more work.

Now look closely at these two branches of the Coco tree: they arrive at the same remaining suffix. That means we are solving the same subproblem again and again.

That is the core issue with naive recursion: repeated subproblems. You can explore any tree you want using the tool below.

Memoization Implementation

We don’t need a brand-new algorithm. We can keep the exact same recursive logic with slicing, and just add a cache.

memo: dict[str, bool] = {}

def is_elemental(name: str) -> bool:
    name = name.lower()

    if name in memo:
        return memo[name]

    if name == "":
        return True

    if name[:1] in ELEMENTS and is_elemental(name[1:]):
        memo[name] = True
        return True

    if len(name) >= 2 and name[:2] in ELEMENTS and is_elemental(name[2:]):
        memo[name] = True
        return True

    memo[name] = False
    return False

This is the same function as before, plus memoization. The key idea is: each remaining suffix (for example "coco", "oco", "co") is solved once, then reused.

Dynamic Programming (Iterative)

We have solved the problem using recursion with memoization. This works well for relatively large inputs, but we hit recursion limits for very long names. So there is a risk of hitting a Python RecursionError if the name is too long.

We can solve the problem iteratively. Instead of asking “Can we form the rest of the name starting from here?”, we can build the solution from left to right.

We can use an array of booleans, let’s call it dp, where each position dp[i] tells us if the prefix of length i is a valid elemental name.

• dp[0] is True (an empty name is valid).
• Then we iterate through the name. If we are at a valid position i (meaning dp[i] is true), we try to extend it:
  • Can we add a 1-letter element? If name[i:i+1] is an element, then dp[i+1] becomes True.
  • Can we add a 2-letter element? If name[i:i+2] is an element, then dp[i+2] becomes True.

By the end of the loop, if the last position dp[n] is True, then the whole name is elemental. This approach avoids recursion limits and is often more efficient in practice.

ELEMENTS = {
    'h','he', ...
}

def is_elemental(name):
    name = name.lower()
    n = len(name)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(n):
        if dp[i]:
            if i + 1 <= n and name[i:i+1] in ELEMENTS:
                dp[i+1] = True
            if i + 2 <= n and name[i:i+2] in ELEMENTS:
                dp[i+2] = True

    return dp[n]

Solution

Test your implementation with the code editor below.

Below, your function will be executed against some test cases and the results will be shown.

Is your name elemental?

Try your own name below and see every possible decomposition with chemical symbols.

Complexity Analysis

The core logic of the recursive algorithm (assuming memoization) is linear, $\mathcal{O}(n)$, because there are $n$ distinct subproblems (suffixes starting at each index), and each subproblem takes constant time to process.

However, in our implementation, we use slicing to create these subproblems. For example, name[1:] creates a new string without the first character. Because strings in Python are immutable, the slicing operation takes $\mathcal{O}(n)$ time, where $n$ is the length of the string being sliced.

Since we perform slicing at each level of recursion, and in the worst case we could have a recursion depth of $\mathcal{O}(n)$, the overall complexity of this implementation becomes $\mathcal{O}(n^2)$ due to the hidden cost of slicing.

However, in practice, this $\mathcal{O}(n^2)$ complexity is rarely the bottleneck for this recursive implementation because Python’s maximum recursion depth limits us to relatively short strings before the quadratic cost of slicing becomes significant.

If we really want to avoid this overhead and restore the true $\mathcal{O}(n)$ complexity for larger inputs (e.g. using an iterative approach), we can pass an integer index as a parameter instead of slicing the string. This way, we track where the current subproblem starts without copying the string data.

The dynamic programming (iterative) solution we discussed earlier is linear because it avoids sliding the rest of the string at each step. It only creates slices of 1 or 2 characters. Space complexity is also $\mathcal{O}(n)$ due to the dp array.

References

• Worder To search for words formed with single-letter elements: BCFHIKNOPSUVWY
• Elemental - Codeforces Problem that inspired this video.
• Presentation Version with visualizations and notes.