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.
"H2O" and "H2O2" are possible, but "H1O2" is impossible.Two formulas are concatenated together to produce another formula.
"H2O2He3Mg4" is also a formula.A formula placed in parentheses, and a count (optionally added) is also a formula.
"(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 <= 1000formula consists of English letters, digits, '(', and ')'.formula is always valid.#726 Number of Atoms requires parsing a chemical formula and returning the count of each atom in sorted order. The key challenge is correctly handling nested parentheses and multipliers. A common strategy is to use a stack to manage scopes created by parentheses. As you scan the string, parse element names (capital letter followed by lowercase letters) and their numeric counts.
When an opening parenthesis appears, push a new map onto the stack to represent a new scope. When a closing parenthesis is encountered, compute the multiplier that follows it, multiply all atom counts in that scope, and merge them with the previous map. A hash map helps track frequencies efficiently. After processing the full string, the final map contains the total atom counts. The atoms are then sorted lexicographically to construct the output string.
This parsing approach processes the formula in a single pass, with additional cost for sorting the final atom names.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack + Hash Map Parsing | O(n log k) | O(n) |
Teacher's Pet
Use these hints if you're stuck. Try solving on your own first.
To parse formula[i:], when we see a `'('`, we will parse recursively whatever is inside the brackets (up to the correct closing ending bracket) and add it to our count, multiplying by the following multiplicity if there is one. Otherwise, we should see an uppercase character: we will parse the rest of the letters to get the name, and add that (plus the multiplicity if there is one.)
This approach uses a recursive parsing strategy combined with a stack to handle the nested nature of formulas within parenthesis. When encountering a parenthesis, we call the function recursively to process the sub-formula, using the stack to apply multipliers correctly once recursion unwinds back to the outer level.
Time Complexity: O(n), where n is the length of the formula, since we parse through each character once.
Space Complexity: O(n), due to the recursion stack and the storage of atom counts.
1import java.util.*;
2
3public class Solution {
4 public String countOfAtoms(String formula) {
5 Map<String, Integer> map = parseFormula(formula, new int[]{0});
6 StringBuilder res = new StringBuilder();
7 for (String name : map.keySet()) {
8 res.append(name);
9 int count = map.get(name);
10 if (count > 1) res.append(count);
11 }
12 return res.toString();
13 }
14
15 private Map<String, Integer> parseFormula(String formula, int[] index) {
16 Map<String, Integer> count = new TreeMap<>();
17 while (index[0] < formula.length()) {
18 char current = formula.charAt(index[0]);
19 if (current == '(') {
20 index[0]++;
21 Map<String, Integer> subMap = parseFormula(formula, index);
22 int multiplier = 1, start = index[0];
23 while (index[0] < formula.length() && Character.isDigit(formula.charAt(index[0]))) {
24 index[0]++;
25 }
26 if (start < index[0]) {
27 multiplier = Integer.parseInt(formula.substring(start, index[0]));
28 }
29 for (String key : subMap.keySet()) {
30 count.put(key, count.getOrDefault(key, 0) + subMap.get(key) * multiplier);
31 }
32 } else if (current == ')') {
33 index[0]++;
34 return count;
35 } else {
36 int start = index[0]++;
37 while (index[0] < formula.length() && Character.isLowerCase(formula.charAt(index[0]))) {
38 index[0]++;
39 }
40 String name = formula.substring(start, index[0]);
41 start = index[0];
42 while (index[0] < formula.length() && Character.isDigit(formula.charAt(index[0]))) {
43 index[0]++;
44 }
45 int multiplicity = (start < index[0]) ? Integer.parseInt(formula.substring(start, index[0])) : 1;
46 count.put(name, count.getOrDefault(name, 0) + multiplicity);
47 }
48 }
49 return count;
50 }
51}
52In Java, we similarly implement a recursive parsing function parseFormula that processes the input formula. A pointer encapsulated in an array is used to track the current index. We utilize a TreeMap for atom counts to automatically order keys alphabetically. The function handles character parsing, and uses recursion to manage the nesting of expressions within parentheses, applying multipliers as needed.
This approach leverages an iterative stack-based strategy to process the formula without recursion. By using an explicit stack, the nested structure is managed more explicitly by keeping track of counts at each level of parentheses, applying multipliers when unwinding back.
Time Complexity: O(n), traversing through the formula.
Space Complexity: O(n), due to the stack's and map's memory usage.
1function countOfAtoms(formula) {
2 let
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The problem requires the final output to list atoms in lexicographical order. After computing the total counts of each atom using maps and stacks, sorting ensures the output follows the required alphabetical order.
Yes, parsing and stack-based problems like Number of Atoms are common in FAANG-style interviews. They test a candidate's ability to handle strings, nested structures, and data structure design efficiently.
The optimal approach uses a stack combined with hash maps to simulate nested scopes created by parentheses. As the formula is parsed, atom counts are accumulated and multiplied when closing parentheses are encountered. Finally, atoms are sorted lexicographically to produce the required output format.
A stack is ideal for managing nested parentheses while parsing the chemical formula. Each stack level maintains a hash map that tracks atom counts for that scope, allowing easy merging when the scope ends.
We use a stack to handle nested elements in the formula and JavaScript's object to manage atom counts. When encountering a '(', a new object is pushed onto the stack, handling atoms encountered as per usual. On encountering a ')', we pop the object, multiply its counts by the number following the bracket (if any), and merge the result into the object below it on the stack. Finally, the sorted atom counts are used to create the output string.