LeetCode Solutions Blog

Number of Atoms

Number: 726

Difficulty: Hard

Paid? No

Problem Description

Given a chemical formula as a string, return a string that represents the count of each atom in sorted order. The formula may include atoms with optional counts, concatenated formulas, and nested formulas enclosed in parentheses where the entire group may have a multiplier.

Key Insights

Use a stack to manage nested groups represented by parentheses.
Parse atom names starting with an uppercase letter followed by lowercase letters.
Read optional digits that represent counts, defaulting to 1 if no digits appear.
When encountering a closing parenthesis, multiply all counts in the group by the multiplier that follows and merge with the previous group.
Finally, sort the atoms lexicographically and build the result string.

Space and Time Complexity

Time Complexity: O(n * log k) where n is the length of the formula and k is the number of unique atoms (due to sorting). Space Complexity: O(n + k) for the stack and the hash map used to store atom counts.

Solution

The solution iterates through the formula with a pointer, using a stack to track counts at each level. Each time an opening parenthesis is encountered, a new hash map is pushed onto the stack. When a closing parenthesis is reached, the current level's counts are popped, multiplied by the following multiplier (if any), and merged with the previous level. Atoms are processed by reading the uppercase letter and any subsequent lowercase letters, then parsing an optional count. After processing, the final map is sorted by atom names and concatenated into the result string.

Code Solutions

# Python implementation for Number of Atoms

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        # Initialize stack with a default dictionary for the outermost level
        stack = [{}]
        i, n = 0, len(formula)
        
        while i < n:
            if formula[i] == '(':
                # Start a new group; push an empty dictionary
                stack.append({})
                i += 1
            elif formula[i] == ')':
                # End of a group; pop top dictionary
                group = stack.pop()
                i += 1
                # Parse multiplier after the closing parenthesis
                multiplier = 0
                while i < n and formula[i].isdigit():
                    multiplier = multiplier * 10 + int(formula[i])
                    i += 1
                if multiplier == 0:
                    multiplier = 1
                # Multiply each atom count in the group and merge with previous level
                for atom, count in group.items():
                    stack[-1][atom] = stack[-1].get(atom, 0) + count * multiplier
            else:
                # Parse atom name starting with an uppercase letter
                start = i
                i += 1  # consume the uppercase letter
                while i < n and formula[i].islower():
                    i += 1
                atom = formula[start:i]
                # Parse the optional count following the atom
                count = 0
                while i < n and formula[i].isdigit():
                    count = count * 10 + int(formula[i])
                    i += 1
                if count == 0:
                    count = 1
                # Add the parsed atom count to the current map
                stack[-1][atom] = stack[-1].get(atom, 0) + count
        
        # The remaining dictionary has the complete atom counts
        final_counts = stack.pop()
        # Create the result string by sorting the atoms lexicographically
        result = []
        for atom in sorted(final_counts.keys()):
            result.append(atom)
            if final_counts[atom] > 1:
                result.append(str(final_counts[atom]))
        return "".join(result)