Number of Atoms
HardPrompt
Given a string formula representing a chemical formula, return the count of each atom.
The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.
One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow.
- For example,
"H2O"and"H2O2"are possible, but"H1O2"is impossible.
Two formulas are concatenated together to produce another formula.
- For example,
"H2O2He3Mg4"is also a formula.
A formula placed in parentheses, and a count (optionally added) is also a formula.
- For example,
"(H2O2)"and"(H2O2)3"are formulas.
Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.
The test cases are generated so that all the values in the output fit in a 32-bit integer.
Example 1:
Input: formula = "H2O"
Output: "H2O"
Explanation: The count of elements are {'H': 2, 'O': 1}.Example 2:
Input: formula = "Mg(OH)2"
Output: "H2MgO2"
Explanation: The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.Example 3:
Input: formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
Explanation: The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.
Constraints:
1 <= formula.length <= 1000formulaconsists of English letters, digits,'(', and')'.formulais always valid.
Approaches
3 approaches with complexity analysis and trade-offs.
A natural way to handle the nested structure of chemical formulas, particularly the parentheses, is through recursion. We can define a function that parses a segment of the formula. When this function encounters an opening parenthesis (, it calls itself to parse the content within the parentheses. This creates a call stack that mirrors the nesting of the formula.
Algorithm
- Use a global index
ito keep track of the current position in the formula string. - Define a recursive function, say
parse(), which will be responsible for parsing a sub-formula (either the main formula or a part enclosed in parentheses). - The
parse()function will return aMap<String, Integer>containing the counts of atoms for the sub-formula it processed. - Inside
parse(), iterate through the string as long as the end is not reached and the character is not a closing parenthesis). - If an opening parenthesis
(is found:- Increment the index
ito move past(. - Make a recursive call to
parse()to handle the nested formula. - After the recursive call returns, the index
iwill be at the corresponding). - Increment
iagain, and parse the number (multiplier) that follows the parenthesis. If no number is present, the multiplier is 1. - Update the counts in the current scope's map by multiplying the counts from the nested map by the multiplier.
- Increment the index
- If an uppercase letter is found:
- Parse the full atom name (e.g.,
H,Mg). - Parse the count that follows. If no count is present, it's 1.
- Add the atom and its count to the current scope's map.
- Parse the full atom name (e.g.,
- The main function initiates the process by calling
parse()on the entire formula. - After receiving the final map of counts, sort the atom names alphabetically and construct the final output string.
Walkthrough
This approach employs a recursive descent parser. A global index i tracks our progress through the formula string. The parse method is the core of the recursion. It creates a map to store atom counts for its current level of parsing (scope). When it sees (, it dives deeper by calling itself. When it returns from a recursive call (after seeing a )), it processes the multiplier for the sub-formula and merges the results into its own map. When it sees an element, it parses the name and count and adds it to its map. The base case for the recursion is encountering a ) or the end of the string.
import java.util.*; class Solution { private int i = 0; public String countOfAtoms(String formula) { Map<String, Integer> counts = parse(formula); List<String> elements = new ArrayList<>(counts.keySet()); Collections.sort(elements); StringBuilder sb = new StringBuilder(); for (String element : elements) { sb.append(element); int count = counts.get(element); if (count > 1) { sb.append(count); } } return sb.toString(); } private Map<String, Integer> parse(String formula) { Map<String, Integer> counts = new HashMap<>(); int n = formula.length(); while (i < n && formula.charAt(i) != ')') { if (formula.charAt(i) == '(') { i++; // Move past '(' Map<String, Integer> nestedCounts = parse(formula); i++; // Move past ')' int start = i; while (i < n && Character.isDigit(formula.charAt(i))) { i++; } int multiplier = start < i ? Integer.parseInt(formula.substring(start, i)) : 1; for (String element : nestedCounts.keySet()) { counts.put(element, counts.getOrDefault(element, 0) + nestedCounts.get(element) * multiplier); } } else { int start = i; i++; // Move past the uppercase letter while (i < n && Character.isLowerCase(formula.charAt(i))) { i++; } String element = formula.substring(start, i); start = i; while (i < n && Character.isDigit(formula.charAt(i))) { i++; } int count = start < i ? Integer.parseInt(formula.substring(start, i)) : 1; counts.put(element, counts.getOrDefault(element, 0) + count); } } return counts; }}Complexity
Time
O(N + K log K), where N is the length of the formula and K is the number of unique elements. The string is parsed in O(N) time. The final sorting of K unique elements takes O(K log K).
Space
O(N * K), where N is the length of the formula and K is the number of unique elements. In the worst-case scenario of deeply nested parentheses like `((...))`, the recursion depth can be up to O(N). Each recursive call stores a map, leading to this complexity.
Trade-offs
Pros
The code structure is intuitive and closely follows the recursive definition of a formula.
Can be easier to reason about for problems with nested structures.
Cons
Can lead to a
StackOverflowErrorfor very deeply nested formulas, although this is unlikely given the problem constraints.Generally has higher memory and performance overhead compared to iterative solutions due to function call stack management.
To avoid the potential pitfalls of recursion, we can use an iterative approach with an explicit stack. The stack will manage the different scopes created by parentheses. Instead of recursive function calls, we push and pop state from our own stack. In this version, we'll store a map of atom counts for each scope on the stack.
Algorithm
- Initialize a stack and push an empty
Map<String, Integer>onto it to represent the global scope. - Iterate through the formula string from left to right using an index
i. - If the character is
(: Push a new empty map onto the stack to represent the new scope. - If the character is
): Pop the map from the top of the stack. This map contains the counts for the sub-formula that just ended. Parse the multiplier that follows the). Multiply all counts in the popped map by this multiplier and add them to the map now at the top of the stack. - If the character is an uppercase letter: Parse the full element name and its count. Add this atom and count to the map currently at the top of the stack.
- After the loop finishes, the stack will contain a single map with the final counts of all atoms.
- Sort the keys of this final map and build the result string.
Walkthrough
This approach simulates the recursion using a stack of maps. Each map on the stack corresponds to a level of parenthesis nesting. We start with one map for the base formula. When we see (, we push a new map for the new scope. When we see ), we finish the current scope, pop its map, apply the necessary multiplier, and merge the results into the parent scope's map (the new top of the stack). This avoids deep recursion and gives us more direct control over the process.
import java.util.*; class Solution { public String countOfAtoms(String formula) { Stack<Map<String, Integer>> stack = new Stack<>(); stack.push(new HashMap<>()); int n = formula.length(); int i = 0; while (i < n) { char c = formula.charAt(i); if (c == '(') { stack.push(new HashMap<>()); i++; } else if (c == ')') { Map<String, Integer> top = stack.pop(); i++; int start = i; while (i < n && Character.isDigit(formula.charAt(i))) { i++; } int multiplier = start < i ? Integer.parseInt(formula.substring(start, i)) : 1; Map<String, Integer> prev = stack.peek(); for (String element : top.keySet()) { prev.put(element, prev.getOrDefault(element, 0) + top.get(element) * multiplier); } } else { int start = i; i++; while (i < n && Character.isLowerCase(formula.charAt(i))) { i++; } String element = formula.substring(start, i); start = i; while (i < n && Character.isDigit(formula.charAt(i))) { i++; } int count = start < i ? Integer.parseInt(formula.substring(start, i)) : 1; stack.peek().put(element, stack.peek().getOrDefault(element, 0) + count); } } Map<String, Integer> finalCounts = stack.pop(); List<String> elements = new ArrayList<>(finalCounts.keySet()); Collections.sort(elements); StringBuilder sb = new StringBuilder(); for (String element : elements) { sb.append(element); int count = finalCounts.get(element); if (count > 1) { sb.append(count); } } return sb.toString(); }}Complexity
Time
O(N + K log K). We perform a single pass through the formula string, and the final sort takes O(K log K).
Space
O(N + K). The total number of entries across all maps on the stack is bounded by O(N), and the final map holds K unique elements.
Trade-offs
Pros
Avoids recursion and the risk of stack overflow.
Iterative solutions are often more efficient in terms of memory and speed than their recursive counterparts.
Cons
Storing entire maps on the stack can be memory-intensive if there are many nested groups with many unique elements inside each.
The logic for merging maps can be slightly more complex than other iterative approaches.
The most efficient approach involves a single pass from right to left. This clever trick simplifies how multipliers are handled. When parsing from the right, any number we encounter is a multiplier for the element or group immediately to its left. We can use a stack to keep track of the cumulative multiplier for the current scope (i.e., how many times the current group is repeated). This avoids storing entire maps on the stack, making it very space-efficient.
Algorithm
- Use a
TreeMapto store the final counts, which keeps the elements sorted automatically. - Use a stack to store integer multipliers. Initialize it by pushing
1(the base multiplier). - Iterate through the formula string from right to left.
- Maintain a
multipliervariable, initialized to1, to hold the count of the item immediately to the right. - If a digit is found: Parse the entire number. This number becomes the current
multiplier. - If a
)is found: This marks the start of a group (from the right). The currentmultiplierapplies to this whole group. Pushstack.peek() * multiplieronto the stack. Then, resetmultiplierto1. - If a
(is found: This marks the end of a group. Pop from the multiplier stack. - If a letter is found: Parse the full element name (backwards). Add this element to the
TreeMapwith a count ofmultiplier * stack.peek(). Resetmultiplierto1. - After the loop, the
TreeMapcontains the final, sorted counts. Build the output string from it.
Walkthrough
By iterating from right to left, we can resolve multipliers as we see them. A stack stores the active multipliers for the nested groups. For example, in (OH)2, when we parse from the right, we first see 2. This 2 will multiply everything inside the (). We push this multiplier onto a stack. Then, as we parse H and O, we multiply their counts (which is 1 by default) by the multiplier at the top of the stack (which is 2). This method is highly efficient as the stack only needs to store integers, not complex map objects.
Using a TreeMap for the final counts is a convenient way to handle the sorting requirement, as it keeps keys sorted automatically.
import java.util.*; class Solution { public String countOfAtoms(String formula) { int n = formula.length(); Stack<Integer> stack = new Stack<>(); stack.push(1); Map<String, Integer> counts = new TreeMap<>(); int i = n - 1; int multiplier = 1; while (i >= 0) { char c = formula.charAt(i); if (Character.isDigit(c)) { int end = i; while (i >= 0 && Character.isDigit(formula.charAt(i))) { i--; } multiplier = Integer.parseInt(formula.substring(i + 1, end + 1)); } else if (c == ')') { stack.push(stack.peek() * multiplier); multiplier = 1; i--; } else if (c == '(') { stack.pop(); i--; } else { // An uppercase letter int end = i; i--; // Move past the uppercase letter while (i >= 0 && Character.isLowerCase(formula.charAt(i))) { i--; } String element = formula.substring(i + 1, end + 1); counts.put(element, counts.getOrDefault(element, 0) + multiplier * stack.peek()); multiplier = 1; } } StringBuilder sb = new StringBuilder(); for (Map.Entry<String, Integer> entry : counts.entrySet()) { sb.append(entry.getKey()); if (entry.getValue() > 1) { sb.append(entry.getValue()); } } return sb.toString(); }}Complexity
Time
O(N log K). The single pass takes O(N), and each of the (at most N) map operations takes O(log K) time for a `TreeMap`. If a `HashMap` were used, it would be O(N + K log K) due to the final sorting step.
Space
O(N + K). The stack depth is at most O(N) (for nested parentheses), and the final map stores K unique elements.
Trade-offs
Pros
Most efficient in terms of space complexity as the stack only stores integers.
Single-pass iterative solution that is robust and fast.
The logic is elegant once the right-to-left parsing concept is understood.
Cons
Parsing from right to left can be less intuitive than the standard left-to-right direction.
Solutions
Solution
class Solution {public String countOfAtoms(String formula) { StringBuffer sb = new StringBuffer(); sb.append(formula.charAt(0)); char prevC = formula.charAt(0); int length = formula.length(); for (int i = 1; i < length; i++) { char c = formula.charAt(i); boolean flag = Character.isLowerCase(c) || Character.isDigit(c) && Character.isDigit(prevC); if (!flag) sb.append(' '); sb.append(c); prevC = c; } String[] array = sb.toString().split(" "); Stack<String> stack = new Stack<String>(); int arrayLength = array.length; for (int i = 0; i < arrayLength; i++) { String str = array[i]; if (str.equals(")")) { if (i < arrayLength - 1 && Character.isDigit(array[i + 1].charAt(0))) stack.push(str); else { Stack<String> tempStack = new Stack<String>(); while (!stack.peek().equals("(")) tempStack.push(stack.pop()); stack.pop(); while (!tempStack.isEmpty()) stack.push(tempStack.pop()); } } else if (Character.isDigit(str.charAt(0))) { int count = Integer.parseInt(str); String prev = stack.pop(); if (prev.equals(")")) { Stack<String> tempStack = new Stack<String>(); while (!stack.peek().equals("(")) { String element = stack.pop(); int index = element.indexOf(','); if (index >= 0) { String atom = element.substring(0, index); int atomCount = Integer.parseInt(element.substring(index + 1)) * count; tempStack.push(atom + "," + atomCount); } else tempStack.push(element + "," + str); } stack.pop(); while (!tempStack.isEmpty()) stack.push(tempStack.pop()); } else { String curStr = prev + "," + str; stack.push(curStr); } } else stack.push(str); } TreeMap<String, Integer> map = new TreeMap<String, Integer>(); while (!stack.isEmpty()) { String atomCount = stack.pop(); int index = atomCount.indexOf(','); if (index >= 0) { String atom = atomCount.substring(0, index); int count = Integer.parseInt(atomCount.substring(index + 1)); count += map.getOrDefault(atom, 0); map.put(atom, count); } else { int count = map.getOrDefault(atomCount, 0) + 1; map.put(atomCount, count); } } StringBuffer output = new StringBuffer(); Set<String> keySet = map.keySet(); for (String atom : keySet) { int count = map.get(atom); output.append(atom); if (count > 1) output.append(count); } return output.toString(); }}/** * @param {string} formula * @return {string} */ var countOfAtoms = function (formula) { const getCount = (formula, factor = 1) => { const n = formula.length; const cnt = {}; const s = []; let [atom, c] = ["", 0]; for (let i = 0; i <= n; i++) { if (formula[i] === " ( ") { const stk = [" ( "]; let j = i; while (stk.length) { j++; if (formula[j] === " ( ") stk.push(" ( "); else if (formula[j] === " ) ") stk.pop(); } const molecule = formula.slice(i + 1, j); const nextFactor = []; while (isDigit(formula[++j])) { nextFactor.push(formula[j]); } const nextC = getCount(molecule, +nextFactor.join("") || 1); for (const [atom, c] of Object.entries(nextC)) { cnt[atom] = (cnt[atom] ?? 0) + c * factor; } i = j - 1; continue; } if (s.length && (!formula[i] || isUpper(formula[i]))) { [atom, c] = getAtom(s); c *= factor; cnt[atom] = (cnt[atom] ?? 0) + c; s.length = 0; } s.push(formula[i]); } return cnt; }; return Object.entries(getCount(formula)) .sort(([a], [b]) => a.localeCompare(b)) .map(([a, b]) => (b > 1 ? a + b : a)) .join(""); };const regex = { atom: / (\D + )(\d + )? /, isUpper: / [ A-Z ] +/ };const getAtom = (s) => { const [_, atom, c] = regex.atom.exec(s.join("")); return [atom, c ? +c : 1];};const isDigit = (ch) => !Number.isNaN(Number.parseInt(ch));const isUpper = (ch) => regex.isUpper.test(ch);class Solution (object): def countOfAtoms(self, formula): """ :type formula: str :rtype: str """ count = self . dfs(formula) res = "" for atom, num in sorted(count . items()): if num == 1: res += atom else: res += atom + str(num) return res def dfs(self, formula): count = collections . Counter() if not formula: return count i = 0 while i < len(formula): if formula[i]. isalpha(): # 首字母是英文字符 atom = formula [ i ] atomNum = 0 # 找到这个元素所有字符 i += 1 while i < len ( formula ) and formula [ i ]. isalpha () and formula [ i ]. islower (): atom += formula [ i ] i += 1 while i < len ( formula ) and formula [ i ]. isdigit (): # 后面是否有数字 atomNum = 10 * atomNum + int ( formula [ i ]) i += 1 count [ atom ] += 1 if atomNum == 0 else atomNum ＃ 使用加号 elif formula [ i ] == "(" : # 括号匹配 left = i # 左括号位置 parent = 1 # 统计括号个数 while i < len ( formula ) and parent != 0 : i += 1 if formula [ i ] == "(" : parent += 1 elif formula [ i ] == ")" : parent -= 1 right = i atomNum = 0 i += 1 while i < len ( formula ) and formula [ i ]. isdigit (): # 后面是否有数字 atomNum = 10 * atomNum + int ( formula [ i ]) i += 1 innerCount = self . dfs ( formula [ left + 1 : right ]) for c , n in innerCount . items (): count [ c ] += n * atomNum count += self . dfs ( formula [ i + 1 :]) return count// OJ: https://leetcode.com/problems/number-of-atoms/ // Time: O(N^2) // Space: O(N) class Solution { int N ; int readNum ( string & s , int & i ) { int cnt = 0 ; while ( i < N && isdigit ( s [ i ])) cnt = cnt * 10 + ( s [ i ++ ] - '0' ); return cnt ? cnt : 1 ; } map < string , int > dfs ( string & s , int & i , bool isInParens = false ) { map < string , int > m ; if ( isInParens ) ++ i ; while ( i < N && s [ i ] != ')' ) { if ( s [ i ] == '(' ) { auto mm = dfs ( s , i , true ); for ( auto & p : mm ) m [ p . first ] += p . second ; } else { string symbol = string ( 1 , s [ i ++ ]); while ( i < N && islower ( s [ i ])) symbol += s [ i ++ ]; m [ symbol ] += readNum ( s , i ); } } if ( isInParens ) { ++ i ; int cnt = readNum ( s , i ); for ( auto & p : m ) p . second *= cnt ; } return m ; } public: string countOfAtoms ( string formula ) { N = formula . size (); int i = 0 ; auto m = dfs ( formula , i ); string ans ; for ( auto & p : m ) ans += p . first + ( p . second > 1 ? to_string ( p . second ) : "" ); return ans ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.