Number of Atoms
Hard · Stack & Strings · Hash Table · String · Stack · Sorting
Problem
You are given a chemical formula as a string. Return how many of each atom it contains.
- An atom name is an uppercase letter followed by zero or more lowercase letters, such as H, Mg or Uue.
- A name may be followed by a count of 2 or more (no leading zeros). With no count, the atom appears once: "H2O" is written that way, never "H2O1".
- Formulas can be written one after another, as in "H2O2He3Mg4", and a formula can be wrapped in parentheses followed by an optional count, as in "(H2O2)" or "(H2O2)3", which multiplies everything inside.
Return a string listing every atom name in sorted order (by character code, so "B" comes before "Be" and "Ca"), each followed by its total count when that count is more than 1.
Examples
Input: formula = "H2SO4" Output: "H2O4S"
Two hydrogen, four oxygen and one sulfur atom, listed in sorted order.
Input: formula = "Fe2(SO4)3" Output: "Fe2O12S3"
The group SO4 is taken three times: 3 sulfur and 12 oxygen.
Input: formula = "(OH)2Ca" Output: "CaH2O2"
The OH group is doubled, and Ca appears once.
Constraints
- 1 <= len(formula) <= 1000
- formula consists of English letters, digits, '(' and ')'
- formula is valid, and no group is empty
- Every count, and every atom total, fits in a 32-bit signed integer
Approaches
- Left to right with a stack of counters — time O(n · a + a log a), space O(n · a) in the worst case
Follow-up
What if you needed one number, such as the formula's weight, rather than a listing? The right-to-left scan can add weight · count · product per atom without building any map; see the use case "Total weight of a formula".
Related problems
Start free on Cariara · Coding problems · System design studio
