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
Difficulty
and has an acceptance rate of about 65% (200k+ submissions).
Typical patterns to solve this problem:
- Hash Table
- Sorting
- Stack
- String
AI Disclaimer
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.
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:
-
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 -
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. -
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
12are 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
MgorFeremain 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
partslist, leadingdeeperto 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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 471: Encode String with Shortest Length
- problem 736: Parse Lisp Expression
Solved On The Same Day
- problem 2104: Sum of Subarray Ranges
- problem 3153: Sum of Digit Differences of All Pairs
- problem 600: Non-negative Integers without Consecutive Ones
- problem 879: Profitable Schemes
Extra
- 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