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.
1from collections import defaultdict
2
3def count_of_atoms(formula: str) -> str:
4 def parse_formula(index):
5 count = defaultdict(int)
6 while index < len(formula):
7 if formula[index] == '(':
8 sub_count, index = parse_formula(index + 1)
9 multiplier = 1
10 start = index
11 while index < len(formula) and formula[index].isdigit():
12 index += 1
13 if index > start:
14 multiplier = int(formula[start:index])
15 for atom in sub_count:
16 count[atom] += sub_count[atom] * multiplier
17 elif formula[index] == ')':
18 return count, index + 1
19 else:
20 i = index
21 index += 1
22 while index < len(formula) and formula[index].islower():
23 index += 1
24 atom = formula[i:index]
25 start = index
26 while index < len(formula) and formula[index].isdigit():
27 index += 1
28 multiplicity = int(formula[start:index] or 1)
29 count[atom] += multiplicity
30 return count, index
31
32 total_count, _ = parse_formula(0)
33 sorted_atoms = sorted(total_count.keys())
34 return ''.join([f"{atom}{total_count[atom] if total_count[atom] > 1 else ''}" for atom in sorted_atoms])
35We create a recursive function parse_formula that tracks the current index in the formula. We loop through characters, processing each segment as either an atom, number, opening parenthesis, or closing parenthesis. For each atom or sub-formula, we determine its count and add it to a dictionary, which accumulates the counts of each atom in the current context. When encountering a closing parenthesis, we return from the recursion with the accumulated counts for that segment to be multiplied accordingly. Finally, the main function uses a sorted list of atoms for output formatting.
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.
1#include <iostream>
2#include <map>
3#include <stack>
4#include <string>
5#include <cctype>
using namespace std;
string countOfAtoms(string formula) {
stack<map<string, int>> stk;
map<string, int> current_map;
int i = 0;
while (i < formula.length()) {
if (formula[i] == '(') {
stk.push(current_map);
current_map.clear();
i++;
} else if (formula[i] == ')') {
i++;
int start = i, multiplicity = 1;
while (i < formula.length() && isdigit(formula[i])) i++;
if (start < i) multiplicity = stoi(formula.substr(start, i - start));
if (!stk.empty()) {
map<string, int> temp_map = current_map;
current_map = stk.top();
stk.pop();
for (auto &pair : temp_map) {
current_map[pair.first] += pair.second * multiplicity;
}
}
} else {
int start = i++;
while (i < formula.length() && islower(formula[i])) i++;
string atom = formula.substr(start, i - start);
start = i;
while (i < formula.length() && isdigit(formula[i])) i++;
int multiplicity = (start < i) ? stoi(formula.substr(start, i - start)) : 1;
current_map[atom] += multiplicity;
}
}
string result;
for (auto &pair : current_map) {
result += pair.first + (pair.second > 1 ? to_string(pair.second) : "");
}
return result;
}
int main() {
string formula = "Mg(OH)2";
cout << countOfAtoms(formula) << endl;
return 0;
}
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.
This C++ solution uses an iterative approach with a stack to manage ongoing calculations and resolve nested parentheses structures. A map is maintained for the current level of parsing, storing atom counts and using a stack to save the state when entering new parentheses. On encountering a closing parenthesis, values are multiplied and merged back into the previous level. The std::map is employed for automatic alphabetical ordering of keys.