Number of Atoms - Solution & Explanation

Problem Overview: The formula string represents a chemical compound such as "K4(ON(SO3)2)2". Each atom may have a count, and parentheses indicate grouped multipliers. Your job is to parse the formula, correctly apply nested multipliers, and return the total count of every atom in lexicographic order.

Approach 1: Recursive Parsing with Stack (O(n + k log k) time, O(n) space)

This approach treats the formula like a recursive grammar. When you encounter (, recursively parse the inner expression until the matching ). Each recursive call returns a frequency map of atoms found inside the group. After the closing parenthesis, read the numeric multiplier and multiply all counts in that map before merging them into the parent scope.

A hash table stores atom frequencies during parsing. The parser scans the string character by character, building atom names (uppercase followed by lowercase letters) and their counts. Nested groups naturally map to recursive calls, which keeps the logic clean and mirrors the structure of the formula. After parsing completes, sort the atom names alphabetically using sorting and construct the output string.

This method is intuitive because it directly models the nested structure of chemical formulas. Time complexity is O(n + k log k), where n is the formula length and k is the number of unique atoms that must be sorted.

Approach 2: Iterative Stack-Based Parsing (O(n + k log k) time, O(n) space)

The iterative version replaces recursion with an explicit stack. Each stack frame stores a map of atom counts for the current scope. When you see (, push a new empty map onto the stack. When you encounter ), pop the top map, read the multiplier that follows, scale all counts, and merge them into the previous map.

Atom parsing works the same way as in the recursive approach. Scan an uppercase letter, continue consuming lowercase characters to form the full atom name, then read any digits that represent the count. If no number follows, the count defaults to 1. Add the count to the map on the top of the stack.

This approach avoids recursion depth issues and is often preferred in languages where explicit stack management is clearer. The algorithm still processes each character once, giving O(n) parsing time, and the final step sorts atom keys to build the result string.

Recommended for interviews: The iterative stack-based parser is typically what interviewers expect. It demonstrates strong control over parsing logic, stack usage, and careful handling of nested multipliers. Explaining the recursive idea first shows conceptual understanding of the formula structure, while implementing the stack solution proves you can translate that idea into an efficient, production-style parser.