LeetCode Solutions Blog

Number of Atoms

Difficulty: Hard

Problem Description

Given a string formula representing a chemical formula, return the count of each atom.

Key Insights

The atomic element starts with an uppercase letter followed by zero or more lowercase letters.
A count for the element may follow, which is greater than 1. If the count is 1, no digits will follow.
Formulas may be concatenated, and can also include parentheses with an optional count.
The output should be a string of element counts in sorted order.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the formula string. Space Complexity: O(m), where m is the number of unique atoms in the formula.

Solution

The solution involves using a stack to handle nested parentheses and a hash table (dictionary) to count the occurrences of each atom. We parse the formula character by character:

For each character, if it's an uppercase letter, we identify the atom and check for any subsequent lowercase letters.
After identifying an atom, we check for a number that follows it to determine its count.
If a '(' is encountered, we push the current counts onto the stack and reset the counts for the new formula inside the parentheses.
Upon encountering a ')', we pop the counts from the stack and multiply them by any number that follows the parentheses.
Finally, we sort the atoms and format the output string.

Code Solutions

def countOfAtoms(formula: str) -> str:
    from collections import defaultdict
    import re

    stack = []
    atom_counts = defaultdict(int)
    i = 0

    while i < len(formula):
        if formula[i].isupper():  # Start of a new atom
            j = i + 1
            while j < len(formula) and formula[j].islower():  # Capture lowercase letters
                j += 1
            atom = formula[i:j]
            i = j
            count = 0
            while i < len(formula) and formula[i].isdigit():  # Capture count
                count = count * 10 + int(formula[i])
                i += 1
            atom_counts[atom] += count if count > 0 else 1  # Default count is 1 if no digits

        elif formula[i] == '(':  # Start of a new sub-formula
            stack.append(atom_counts)
            atom_counts = defaultdict(int)
            i += 1

        elif formula[i] == ')':  # End of a sub-formula
            i += 1
            count = 0
            while i < len(formula) and formula[i].isdigit():  # Capture following count
                count = count * 10 + int(formula[i])
                i += 1
            multiplier = count if count > 0 else 1
            for atom, cnt in atom_counts.items():
                atom_counts[atom] = cnt * multiplier
            if stack:
                prev_counts = stack.pop()
                for atom, cnt in atom_counts.items():
                    prev_counts[atom] += cnt
                atom_counts = prev_counts

    # Prepare output
    result = []
    for atom in sorted(atom_counts.keys()):
        count = atom_counts[atom]
        result.append(f"{atom}{count if count > 1 else ''}")
    return ''.join(result)