396. Formula Atom Counter
A chemistry app reads formulas written as text. An element name is one uppercase letter followed by zero or more lowercase letters (for example H, Mg, Uuo). An element may be followed by a count, an integer of at least 2; with no count it appears once. A group in round brackets, which contains at least one element, may also be followed by a count of at least 2 that multiplies everything inside it, and groups can be nested.
Given the text formula, return a string listing every distinct element exactly once, ordered by element name in ascending alphabetical (ASCII) order. After each name write its total number of atoms, but only when that total is greater than 1. For example H2O stays H2O and (OH)2Mg becomes H2MgO2. All counts, including intermediate group totals, fit in a 32-bit signed integer.
Example 1
- Input:
- formula = "Na2(Cu(NH3)4)3Cl"
- Output:
- "ClCu3H36N12Na2"
- Explanation:
Cu(NH3)4 gives N4 H12, repeated 3 times gives N12 H36 and Cu3. With Na2 and Cl, sorted by name: Cl, Cu3, H36, N12, Na2.
Example 2
- Input:
- formula = "((Be2Li)2B)3"
- Output:
- "B3Be12Li6"
- Explanation:
Inside: Be4 Li2, then with B and multiplied by 3 gives Be12, Li6, B3. Sorted: B3Be12Li6.
Constraints
1 ≤ formula.length ≤ 2 * 104
The formula is valid; element names are an uppercase letter followed by lowercase letters; counts are integers ≥ 2 without leading zeros.
Every total fits in a signed 32-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n * d)
- Space
- O(n * d)