Hard

Number of Atoms

099

Given a chemical formula, return the canonical atom count string with atom names sorted alphabetically.

EXAMPLES

Example 1

Input
{
  "formula": "Mg(OH)2"
}

Output
"H2MgO2"

FUNCTION SHAPE

formula: string→string

SOLUTION NOTE

This follows the same recursive parsing pattern as calculators: match parentheses, parse the inner expression, then apply the multiplier after the closing parenthesis.

Reveal reference solution +

pythonREFERENCE

from collections import Counter

def countOfAtoms(self, formula: str) -> str:
    n = len(formula)
    closing = {}
    stack = []
    for i, c in enumerate(formula):
        if c == '(':
            stack.append(i)
        elif c == ')':
            closing[stack.pop()] = i

    def read_number(i):
        start = i
        while i < n and formula[i].isdigit():
            i += 1
        return (int(formula[start:i]) if i > start else 1), i

    def parse(left, right):
        counts = Counter()
        i = left
        while i <= right:
            if formula[i] == '(':
                close = closing[i]
                inner = parse(i + 1, close - 1)
                multiplier, i = read_number(close + 1)
                for atom, count in inner.items():
                    counts[atom] += count * multiplier
            else:
                j = i + 1
                while j <= right and formula[j].islower():
                    j += 1
                atom = formula[i:j]
                multiplier, i = read_number(j)
                counts[atom] += multiplier
        return counts

    counts = parse(0, n - 1)
    return ''.join(atom + (str(count) if count > 1 else '') for atom, count in sorted(counts.items()))

TimeO(n log a)

SpaceO(n)

Open on LeetCode ↗