# Number of Atoms
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-atoms)
Canonical: https://scaleengineer.com/dsa/problems/number-of-atoms
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String, Stack
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [Coupang](https://scaleengineer.com/companies/coupang), [Confluent](https://scaleengineer.com/companies/confluent), [Fastenal](https://scaleengineer.com/companies/fastenal)
---
## Problem
Given a string `formula` representing a chemical formula, return _the count of each atom_.

The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

One or more digits representing that element's count may follow if the count is greater than `1`. If the count is `1`, no digits will follow.

* For example, `"H2O"` and `"H2O2"` are possible, but `"H1O2"` is impossible.

Two formulas are concatenated together to produce another formula.

* For example, `"H2O2He3Mg4"` is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula.

* For example, `"(H2O2)"` and `"(H2O2)3"` are formulas.

Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than `1`), followed by the second name (in sorted order), followed by its count (if that count is more than `1`), and so on.

The test cases are generated so that all the values in the output fit in a **32-bit** integer.

**Example 1:**

**Input:** formula = "H2O"
**Output:** "H2O"
**Explanation:** The count of elements are {'H': 2, 'O': 1}.

**Example 2:**

**Input:** formula = "Mg(OH)2"
**Output:** "H2MgO2"
**Explanation:** The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.

**Example 3:**

**Input:** formula = "K4(ON(SO3)2)2"
**Output:** "K4N2O14S4"
**Explanation:** The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.

**Constraints:**

* `1 <= formula.length <= 1000`
* `formula` consists of English letters, digits, `'('`, and `')'`.
* `formula` is always valid.

# Approaches
## Recursive Parsing
A natural way to handle the nested structure of chemical formulas, particularly the parentheses, is through recursion. We can define a function that parses a segment of the formula. When this function encounters an opening parenthesis `(`, it calls itself to parse the content within the parentheses. This creates a call stack that mirrors the nesting of the formula.
**Time:** O(N + K log K), where N is the length of the formula and K is the number of unique elements. The string is parsed in O(N) time. The final sorting of K unique elements takes O(K log K). · **Space:** O(N * K), where N is the length of the formula and K is the number of unique elements. In the worst-case scenario of deeply nested parentheses like `((...))`, the recursion depth can be up to O(N). Each recursive call stores a map, leading to this complexity.
**Pros:** The code structure is intuitive and closely follows the recursive definition of a formula.; Can be easier to reason about for problems with nested structures.
**Cons:** Can lead to a `StackOverflowError` for very deeply nested formulas, although this is unlikely given the problem constraints.; Generally has higher memory and performance overhead compared to iterative solutions due to function call stack management.
### Explanation
This approach employs a recursive descent parser. A global index `i` tracks our progress through the `formula` string. The `parse` method is the core of the recursion. It creates a map to store atom counts for its current level of parsing (scope). When it sees `(`, it dives deeper by calling itself. When it returns from a recursive call (after seeing a `)`), it processes the multiplier for the sub-formula and merges the results into its own map. When it sees an element, it parses the name and count and adds it to its map. The base case for the recursion is encountering a `)` or the end of the string.

```java
import java.util.*;

class Solution {
    private int i = 0;

    public String countOfAtoms(String formula) {
        Map<String, Integer> counts = parse(formula);
        List<String> elements = new ArrayList<>(counts.keySet());
        Collections.sort(elements);

        StringBuilder sb = new StringBuilder();
        for (String element : elements) {
            sb.append(element);
            int count = counts.get(element);
            if (count > 1) {
                sb.append(count);
            }
        }
        return sb.toString();
    }

    private Map<String, Integer> parse(String formula) {
        Map<String, Integer> counts = new HashMap<>();
        int n = formula.length();

        while (i < n && formula.charAt(i) != ')') {
            if (formula.charAt(i) == '(') {
                i++; // Move past '('
                Map<String, Integer> nestedCounts = parse(formula);
                i++; // Move past ')'
                
                int start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplier = start < i ? Integer.parseInt(formula.substring(start, i)) : 1;

                for (String element : nestedCounts.keySet()) {
                    counts.put(element, counts.getOrDefault(element, 0) + nestedCounts.get(element) * multiplier);
                }
            } else {
                int start = i;
                i++; // Move past the uppercase letter
                while (i < n && Character.isLowerCase(formula.charAt(i))) {
                    i++;
                }
                String element = formula.substring(start, i);

                start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int count = start < i ? Integer.parseInt(formula.substring(start, i)) : 1;
                counts.put(element, counts.getOrDefault(element, 0) + count);
            }
        }
        return counts;
    }
}
```
### Algorithm
- Use a global index `i` to keep track of the current position in the formula string.
- Define a recursive function, say `parse()`, which will be responsible for parsing a sub-formula (either the main formula or a part enclosed in parentheses).
- The `parse()` function will return a `Map<String, Integer>` containing the counts of atoms for the sub-formula it processed.
- Inside `parse()`, iterate through the string as long as the end is not reached and the character is not a closing parenthesis `)`. 
- If an opening parenthesis `(` is found: 
  - Increment the index `i` to move past `(`.
  - Make a recursive call to `parse()` to handle the nested formula.
  - After the recursive call returns, the index `i` will be at the corresponding `)`.
  - Increment `i` again, and parse the number (multiplier) that follows the parenthesis. If no number is present, the multiplier is 1.
  - Update the counts in the current scope's map by multiplying the counts from the nested map by the multiplier.
- If an uppercase letter is found:
  - Parse the full atom name (e.g., `H`, `Mg`).
  - Parse the count that follows. If no count is present, it's 1.
  - Add the atom and its count to the current scope's map.
- The main function initiates the process by calling `parse()` on the entire formula.
- After receiving the final map of counts, sort the atom names alphabetically and construct the final output string.

## Iterative Parsing with a Stack of Maps
To avoid the potential pitfalls of recursion, we can use an iterative approach with an explicit stack. The stack will manage the different scopes created by parentheses. Instead of recursive function calls, we push and pop state from our own stack. In this version, we'll store a map of atom counts for each scope on the stack.
**Time:** O(N + K log K). We perform a single pass through the formula string, and the final sort takes O(K log K). · **Space:** O(N + K). The total number of entries across all maps on the stack is bounded by O(N), and the final map holds K unique elements.
**Pros:** Avoids recursion and the risk of stack overflow.; Iterative solutions are often more efficient in terms of memory and speed than their recursive counterparts.
**Cons:** Storing entire maps on the stack can be memory-intensive if there are many nested groups with many unique elements inside each.; The logic for merging maps can be slightly more complex than other iterative approaches.
### Explanation
This approach simulates the recursion using a stack of maps. Each map on the stack corresponds to a level of parenthesis nesting. We start with one map for the base formula. When we see `(`, we push a new map for the new scope. When we see `)`, we finish the current scope, pop its map, apply the necessary multiplier, and merge the results into the parent scope's map (the new top of the stack). This avoids deep recursion and gives us more direct control over the process.

```java
import java.util.*;

class Solution {
    public String countOfAtoms(String formula) {
        Stack<Map<String, Integer>> stack = new Stack<>();
        stack.push(new HashMap<>());
        int n = formula.length();
        int i = 0;

        while (i < n) {
            char c = formula.charAt(i);
            if (c == '(') {
                stack.push(new HashMap<>());
                i++;
            } else if (c == ')') {
                Map<String, Integer> top = stack.pop();
                i++;
                int start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplier = start < i ? Integer.parseInt(formula.substring(start, i)) : 1;
                Map<String, Integer> prev = stack.peek();
                for (String element : top.keySet()) {
                    prev.put(element, prev.getOrDefault(element, 0) + top.get(element) * multiplier);
                }
            } else {
                int start = i;
                i++;
                while (i < n && Character.isLowerCase(formula.charAt(i))) {
                    i++;
                }
                String element = formula.substring(start, i);

                start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int count = start < i ? Integer.parseInt(formula.substring(start, i)) : 1;
                stack.peek().put(element, stack.peek().getOrDefault(element, 0) + count);
            }
        }

        Map<String, Integer> finalCounts = stack.pop();
        List<String> elements = new ArrayList<>(finalCounts.keySet());
        Collections.sort(elements);

        StringBuilder sb = new StringBuilder();
        for (String element : elements) {
            sb.append(element);
            int count = finalCounts.get(element);
            if (count > 1) {
                sb.append(count);
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Initialize a stack and push an empty `Map<String, Integer>` onto it to represent the global scope.
- Iterate through the formula string from left to right using an index `i`.
- If the character is `(`: Push a new empty map onto the stack to represent the new scope.
- If the character is `)`: Pop the map from the top of the stack. This map contains the counts for the sub-formula that just ended. Parse the multiplier that follows the `)`. Multiply all counts in the popped map by this multiplier and add them to the map now at the top of the stack.
- If the character is an uppercase letter: Parse the full element name and its count. Add this atom and count to the map currently at the top of the stack.
- After the loop finishes, the stack will contain a single map with the final counts of all atoms.
- Sort the keys of this final map and build the result string.

## Optimized Iterative Parsing (Right-to-Left)
The most efficient approach involves a single pass from right to left. This clever trick simplifies how multipliers are handled. When parsing from the right, any number we encounter is a multiplier for the element or group immediately to its left. We can use a stack to keep track of the cumulative multiplier for the current scope (i.e., how many times the current group is repeated). This avoids storing entire maps on the stack, making it very space-efficient.
**Time:** O(N log K). The single pass takes O(N), and each of the (at most N) map operations takes O(log K) time for a `TreeMap`. If a `HashMap` were used, it would be O(N + K log K) due to the final sorting step. · **Space:** O(N + K). The stack depth is at most O(N) (for nested parentheses), and the final map stores K unique elements.
**Pros:** Most efficient in terms of space complexity as the stack only stores integers.; Single-pass iterative solution that is robust and fast.; The logic is elegant once the right-to-left parsing concept is understood.
**Cons:** Parsing from right to left can be less intuitive than the standard left-to-right direction.
### Explanation
By iterating from right to left, we can resolve multipliers as we see them. A stack stores the active multipliers for the nested groups. For example, in `(OH)2`, when we parse from the right, we first see `2`. This `2` will multiply everything inside the `()`. We push this multiplier onto a stack. Then, as we parse `H` and `O`, we multiply their counts (which is 1 by default) by the multiplier at the top of the stack (which is 2). This method is highly efficient as the stack only needs to store integers, not complex map objects.

Using a `TreeMap` for the final counts is a convenient way to handle the sorting requirement, as it keeps keys sorted automatically.

```java
import java.util.*;

class Solution {
    public String countOfAtoms(String formula) {
        int n = formula.length();
        Stack<Integer> stack = new Stack<>();
        stack.push(1);

        Map<String, Integer> counts = new TreeMap<>();

        int i = n - 1;
        int multiplier = 1;

        while (i >= 0) {
            char c = formula.charAt(i);

            if (Character.isDigit(c)) {
                int end = i;
                while (i >= 0 && Character.isDigit(formula.charAt(i))) {
                    i--;
                }
                multiplier = Integer.parseInt(formula.substring(i + 1, end + 1));
            } else if (c == ')') {
                stack.push(stack.peek() * multiplier);
                multiplier = 1;
                i--;
            } else if (c == '(') {
                stack.pop();
                i--;
            } else { // An uppercase letter
                int end = i;
                i--; // Move past the uppercase letter
                while (i >= 0 && Character.isLowerCase(formula.charAt(i))) {
                    i--;
                }
                String element = formula.substring(i + 1, end + 1);
                counts.put(element, counts.getOrDefault(element, 0) + multiplier * stack.peek());
                multiplier = 1;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            sb.append(entry.getKey());
            if (entry.getValue() > 1) {
                sb.append(entry.getValue());
            }
        }

        return sb.toString();
    }
}
```
### Algorithm
- Use a `TreeMap` to store the final counts, which keeps the elements sorted automatically.
- Use a stack to store integer multipliers. Initialize it by pushing `1` (the base multiplier).
- Iterate through the formula string from **right to left**.
- Maintain a `multiplier` variable, initialized to `1`, to hold the count of the item immediately to the right.
- If a digit is found: Parse the entire number. This number becomes the current `multiplier`.
- If a `)` is found: This marks the start of a group (from the right). The current `multiplier` applies to this whole group. Push `stack.peek() * multiplier` onto the stack. Then, reset `multiplier` to `1`.
- If a `(` is found: This marks the end of a group. Pop from the multiplier stack.
- If a letter is found: Parse the full element name (backwards). Add this element to the `TreeMap` with a count of `multiplier * stack.peek()`. Reset `multiplier` to `1`.
- After the loop, the `TreeMap` contains the final, sorted counts. Build the output string from it.

# Solutions
### Java

```java
class Solution {
public
  String countOfAtoms(String formula) {
    StringBuffer sb = new StringBuffer();
    sb.append(formula.charAt(0));
    char prevC = formula.charAt(0);
    int length = formula.length();
    for (int i = 1; i < length; i++) {
      char c = formula.charAt(i);
      boolean flag = Character.isLowerCase(c) ||
                     Character.isDigit(c) && Character.isDigit(prevC);
      if (!flag)
        sb.append(' ');
      sb.append(c);
      prevC = c;
    }
    String[] array = sb.toString().split(" ");
    Stack<String> stack = new Stack<String>();
    int arrayLength = array.length;
    for (int i = 0; i < arrayLength; i++) {
      String str = array[i];
      if (str.equals(")")) {
        if (i < arrayLength - 1 && Character.isDigit(array[i + 1].charAt(0)))
          stack.push(str);
        else {
          Stack<String> tempStack = new Stack<String>();
          while (!stack.peek().equals("("))
            tempStack.push(stack.pop());
          stack.pop();
          while (!tempStack.isEmpty())
            stack.push(tempStack.pop());
        }
      } else if (Character.isDigit(str.charAt(0))) {
        int count = Integer.parseInt(str);
        String prev = stack.pop();
        if (prev.equals(")")) {
          Stack<String> tempStack = new Stack<String>();
          while (!stack.peek().equals("(")) {
            String element = stack.pop();
            int index = element.indexOf(',');
            if (index >= 0) {
              String atom = element.substring(0, index);
              int atomCount =
                  Integer.parseInt(element.substring(index + 1)) * count;
              tempStack.push(atom + "," + atomCount);
            } else
              tempStack.push(element + "," + str);
          }
          stack.pop();
          while (!tempStack.isEmpty())
            stack.push(tempStack.pop());
        } else {
          String curStr = prev + "," + str;
          stack.push(curStr);
        }
      } else
        stack.push(str);
    }
    TreeMap<String, Integer> map = new TreeMap<String, Integer>();
    while (!stack.isEmpty()) {
      String atomCount = stack.pop();
      int index = atomCount.indexOf(',');
      if (index >= 0) {
        String atom = atomCount.substring(0, index);
        int count = Integer.parseInt(atomCount.substring(index + 1));
        count += map.getOrDefault(atom, 0);
        map.put(atom, count);
      } else {
        int count = map.getOrDefault(atomCount, 0) + 1;
        map.put(atomCount, count);
      }
    }
    StringBuffer output = new StringBuffer();
    Set<String> keySet = map.keySet();
    for (String atom : keySet) {
      int count = map.get(atom);
      output.append(atom);
      if (count > 1)
        output.append(count);
    }
    return output.toString();
  }
}

```

### JavaScript

```javascript
/** * @param {string} formula * @return {string} */ var countOfAtoms =
  function (formula) {
    const getCount = (formula, factor = 1) => {
      const n = formula.length;
      const cnt = {};
      const s = [];
      let [atom, c] = ["", 0];
      for (let i = 0; i <= n; i++) {
        if (formula[i] === " ( ") {
          const stk = [" ( "];
          let j = i;
          while (stk.length) {
            j++;
            if (formula[j] === " ( ") stk.push(" ( ");
            else if (formula[j] === " ) ") stk.pop();
          }
          const molecule = formula.slice(i + 1, j);
          const nextFactor = [];
          while (isDigit(formula[++j])) {
            nextFactor.push(formula[j]);
          }
          const nextC = getCount(molecule, +nextFactor.join("") || 1);
          for (const [atom, c] of Object.entries(nextC)) {
            cnt[atom] = (cnt[atom] ?? 0) + c * factor;
          }
          i = j - 1;
          continue;
        }
        if (s.length && (!formula[i] || isUpper(formula[i]))) {
          [atom, c] = getAtom(s);
          c *= factor;
          cnt[atom] = (cnt[atom] ?? 0) + c;
          s.length = 0;
        }
        s.push(formula[i]);
      }
      return cnt;
    };
    return Object.entries(getCount(formula))
      .sort(([a], [b]) => a.localeCompare(b))
      .map(([a, b]) => (b > 1 ? a + b : a))
      .join("");
  };
const regex = { atom: / (\D + )(\d + )? /, isUpper: / [ A-Z ] +/ };
const getAtom = (s) => {
  const [_, atom, c] = regex.atom.exec(s.join(""));
  return [atom, c ? +c : 1];
};
const isDigit = (ch) => !Number.isNaN(Number.parseInt(ch));
const isUpper = (ch) => regex.isUpper.test(ch);

```

### Python

```python
class Solution (object):
    def countOfAtoms(self, formula): """ :type formula: str :rtype: str """ count = self . dfs(formula) res = "" for atom, num in sorted(count . items()): if num == 1: res += atom else: res += atom + str(num) return res def dfs(self, formula): count = collections . Counter() if not formula: return count i = 0 while i < len(formula): if formula[i]. isalpha():  # 首字母是英文字符 atom = formula [ i ] atomNum = 0 # 找到这个元素所有字符 i += 1 while i < len ( formula ) and formula [ i ]. isalpha () and formula [ i ]. islower (): atom += formula [ i ] i += 1 while i < len ( formula ) and formula [ i ]. isdigit (): # 后面是否有数字 atomNum = 10 * atomNum + int ( formula [ i ]) i += 1 count [ atom ] += 1 if atomNum == 0 else atomNum ＃ 使用加号 elif formula [ i ] == "(" : # 括号匹配 left = i # 左括号位置 parent = 1 # 统计括号个数 while i < len ( formula ) and parent != 0 : i += 1 if formula [ i ] == "(" : parent += 1 elif formula [ i ] == ")" : parent -= 1 right = i atomNum = 0 i += 1 while i < len ( formula ) and formula [ i ]. isdigit (): # 后面是否有数字 atomNum = 10 * atomNum + int ( formula [ i ]) i += 1 innerCount = self . dfs ( formula [ left + 1 : right ]) for c , n in innerCount . items (): count [ c ] += n * atomNum count += self . dfs ( formula [ i + 1 :]) return count

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/number-of-atoms/ // Time: O(N^2) // Space: O(N) class Solution { int N ; int readNum ( string & s , int & i ) { int cnt = 0 ; while ( i < N && isdigit ( s [ i ])) cnt = cnt * 10 + ( s [ i ++ ] - '0' ); return cnt ? cnt : 1 ; } map < string , int > dfs ( string & s , int & i , bool isInParens = false ) { map < string , int > m ; if ( isInParens ) ++ i ; while ( i < N && s [ i ] != ')' ) { if ( s [ i ] == '(' ) { auto mm = dfs ( s , i , true ); for ( auto & p : mm ) m [ p . first ] += p . second ; } else { string symbol = string ( 1 , s [ i ++ ]); while ( i < N && islower ( s [ i ])) symbol += s [ i ++ ]; m [ symbol ] += readNum ( s , i ); } } if ( isInParens ) { ++ i ; int cnt = readNum ( s , i ); for ( auto & p : m ) p . second *= cnt ; } return m ; } public: string countOfAtoms ( string formula ) { N = formula . size (); int i = 0 ; auto m = dfs ( formula , i ); string ans ; for ( auto & p : m ) ans += p . first + ( p . second > 1 ? to_string ( p . second ) : "" ); return ans ; } };
```