Problem 726

Abstract / Summary

Combine atoms with same names by adding counts then recursively process values and shorten results.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0726.py

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        # tokenize
        parts = []
        for c in formula:
            if (c.isdigit() and parts[-1].isdigit()) or ("a" <= c <= "z"):
                parts[-1] += c
            else:
                parts.append(c)

        def deeper():
            nonlocal parts
            count = defaultdict(int)

            while parts:
                token = parts.pop(0)

                if   token == "(":
                    # parse brackets
                    nested = deeper()

                    # optional factor
                    factor = 1
                    if parts and parts[0].isdigit():
                        factor = int(parts.pop(0))

                    # add all elements
                    for key, value in nested.items():
                        count[key] += factor * value
                elif token == ")":
                    break
                else:
                    # optional factor
                    factor = 1
                    if parts and parts[0].isdigit():
                        factor = int(parts.pop(0))

                    # add element
                    count[token] += factor

            return count

        # sort
        result = ""
        for name, atoms in sorted(deeper().items()):
            result += name
            if atoms > 1:
                result += str(atoms)

        return result
50 lines | 1479 bytes | submitted May 29, 2024 | GitHub   20% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 65% (200k+ submissions).

Typical patterns to solve this problem:
  • Hash Table
  • Sorting
  • Stack
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The implementation defines a Solution class with a single public method countOfAtoms. The method receives a chemical formula string and returns a canonical representation where each atom appears in alphabetical order followed by its count (omitted when the count is one). The algorithm proceeds in three logical phases: tokenization of the input string, recursive parsing of the token stream to compute atom frequencies, and final assembly of the sorted result.

Tokenization

The first loop walks through every character of the input formula and builds a list called parts. The logic merges consecutive digits into a single numeric token and appends lowercase letters to the preceding token when they belong to an element symbol. The essential fragment is:

parts = []
for c in formula:
    if (c.isdigit() and parts[-1].isdigit()) or ("a" <= c <= "z"):
        parts[-1] += c
    else:
        parts.append(c)

By the end of this phase the formula "Mg(OH)2" becomes ['Mg', '(', 'O', 'H', ')', '2']. This representation simplifies later processing because each token is either a complete element name, a parenthesis, or a whole integer.

Recursive Descent Parsing

A nested helper function deeper performs a depth-first traversal of the token list. It maintains a defaultdict(int) named count that accumulates atom frequencies for the current nesting level. The function repeatedly removes the first token with pop(0) and distinguishes three cases:

  1. Opening parenthesis - The function calls itself recursively to obtain the frequency map of the sub-expression. After the recursive call returns, it checks whether the next token is a digit; if so, that digit becomes a multiplication factor for every atom inside the parentheses. The factor defaults to one when absent. The snippet handling this is:

     if token == "(":
         nested = deeper()
         factor = 1
         if parts and parts[0].isdigit():
             factor = int(parts.pop(0))
         for key, value in nested.items():
             count[key] += factor * value
  2. Closing parenthesis - Encountering ")" signals the end of the current nesting level, causing the function to break out of the loop and return the accumulated map to the caller.

  3. Element token - When the token is an element name, the function looks ahead for an optional numeric token that represents the atom count. If no digit follows, the factor remains one. The element’s count is then added to count:

     else:
         factor = 1
         if parts and parts[0].isdigit():
             factor = int(parts.pop(0))
         count[token] += factor

The recursion naturally handles arbitrarily deep nesting, such as "K4(ON(SO3)2)2", by creating a new count dictionary for each level and propagating multiplied values upward.

Sorting and Result Construction

After the outermost call to deeper finishes, the method receives a flat dictionary mapping each atom to its total quantity. The final step iterates over the items in alphabetical order, concatenating the atom name and its count (omitting the count when it equals one). The relevant code is:

result = ""
for name, atoms in sorted(deeper().items()):
    result += name
    if atoms > 1:
        result += str(atoms)
return result

The use of Python’s built-in sorted guarantees the required lexicographic ordering without additional bookkeeping.

Edge Cases Handled

The algorithm gracefully deals with several subtle situations:

  • Multi-digit multipliers - Because the tokenization phase merges consecutive digits, numbers like 12 are treated as a single token, allowing correct multiplication of atom counts.
  • Elements with two-letter symbols - Lowercase letters are appended to the preceding token, so symbols such as Mg or Fe remain intact.
  • Implicit multipliers - When a number does not follow an element or a closing parenthesis, the code defaults the factor to one, correctly interpreting formulas like "H2O" and "NaCl".
  • Nested parentheses - The recursive design automatically accumulates counts from inner groups before applying outer multipliers, handling deep nesting without special case logic.
  • Empty or trivial formulas - An empty string would produce an empty parts list, leading deeper to return an empty dictionary and ultimately an empty result string, which is a consistent outcome.

Performance Optimizations

Several choices contribute to efficient execution:

  • Use of defaultdict(int) - This eliminates the need for explicit existence checks before incrementing atom counts, reducing overhead in the innermost loops.
  • In-place token consumption - By popping tokens from the front of parts, the parser avoids maintaining separate indices or slices, keeping the state compact.
  • Early factor extraction - The code checks for a following digit immediately after processing a parenthesis or an element, preventing a second pass over the token list to apply multipliers.
  • Single pass recursion - Each token is examined exactly once during the depth-first traversal, ensuring linear processing relative to the number of tokens.
  • Deferred sorting - Sorting is performed only once after the full frequency map is built, rather than repeatedly during parsing, which minimizes sorting overhead.

These design decisions collectively ensure that the method scales well with the length and complexity of the input formula while keeping the implementation concise.

written by openai gpt

ELI5 - Simplified Explanation

Think of this code like a tiny robot sorting through a box of building blocks. The chemical formula is just a long string of letters and numbers, like a secret message. First, the robot picks up the string and chops it into small, easy pieces. It keeps letters together if they are part of the same name and makes sure the numbers stay attached to the items they belong to.

Next, the robot starts looking inside parentheses. If it sees an opening bracket, it dives deeper to count everything tucked inside. It keeps track of how many of each block it finds. If a number is sitting right after a block or a group, the robot multiplies the count to know exactly how many pieces are really there. It does this over and over until everything is carefully counted.

Once the robot has finished its job, it organizes the final list by putting the names in alphabetical order, just like tidying up toys on a shelf. If there are many of one kind of block, it sticks the number on the end so everyone knows exactly how many are in the pile. If there is only one of something, it just leaves the name alone, which keeps everything clean and simple. Everything gets perfectly arranged and ready to display.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 6 | μ = 5.69 | σ = 1.83

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java JS Python TS
LeetcodeHelp C++ Java Python
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
everthis JS
gouthampradhan Java
halfrost Go
JoshCrozier JS
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
varunu28 Java
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Java, JavaScript, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
gouthampradhan Java
halfrost Go
JoshCrozier JavaScript
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
varunu28 Java
wisdompeak C++
31 links | 18 authors | 8 languages

Videos

14 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

5 solutions   May 29, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality