Number of Atoms

Hard
1422.

Number of Atoms

Number of Atoms is a hard coding problem on strings, hash table and sorting, asked in Amazon, Google and Apple interviews.

A chemical formula is built from these pieces:

  • An atom name: one uppercase letter followed by zero or more lowercase letters, such as H, Mg or Zn.
  • An optional count right after an atom: a number of at least 2 (a count of 1 is never written). H2O has two hydrogen atoms and one oxygen atom.
  • Formulas can be concatenated (H2O2He3Mg4) or wrapped in parentheses with an optional count that multiplies everything inside ((H2O2)3).

Return the number of atoms of each element as a string: the element names in sorted (lexicographic, by character code) order, each followed by its count if that count is more than 1.

Example 1

Input
formula = "C6H12O6"
Output
C6H12O6

Example 2

Input
formula = "Fe2(SO4)3"
Output
Fe2O12S3
Explanation
The group SO4 is tripled: 3 sulfur and 12 oxygen atoms.

Example 3

Input
formula = "(NH4)3PO4"
Output
H12N3O4P

Constraints

  • 1 <= formula.length <= 1000
  • formula consists of English letters, digits, '(' and ')'
  • formula is always valid
  • Every count in the answer fits in a 32-bit integer
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} formula
 * @return {string}
 */
var countOfAtoms = function(formula) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Atoms — Solution in Python, Java & C++

Number of Atoms solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on strings and hash table.

Number of Atoms is a hard coding problem on strings, hash table and sorting, asked in Amazon, Google and Apple interviews.

Problem statement

A chemical formula is built from these pieces:

  • An atom name: one uppercase letter followed by zero or more lowercase letters, such as H, Mg or Zn.
  • An optional count right after an atom: a number of at least 2 (a count of 1 is never written). H2O has two hydrogen atoms and one oxygen atom.
  • Formulas can be concatenated (H2O2He3Mg4) or wrapped in parentheses with an optional count that multiplies everything inside ((H2O2)3).

Return the number of atoms of each element as a string: the element names in sorted (lexicographic, by character code) order, each followed by its count if that count is more than 1.

Example 1

Input: formula = "C6H12O6"
Output: C6H12O6

Example 2

Input: formula = "Fe2(SO4)3"
Output: Fe2O12S3
Explanation: The group SO4 is tripled: 3 sulfur and 12 oxygen atoms.

Example 3

Input: formula = "(NH4)3PO4"
Output: H12N3O4P

Constraints

  • 1 <= formula.length <= 1000
  • formula consists of English letters, digits, '(' and ')'
  • formula is always valid
  • Every count in the answer fits in a 32-bit integer

Hints for Number of Atoms

  1. Hint 1

    A count after ) multiplies every atom inside that group, and groups can nest.

  2. Hint 2

    Reading the formula from right to left, you see each multiplier before the atoms it applies to.

  3. Hint 3

    Scan right to left with a stack of multipliers: digits build a pending number; ) pushes top × number; ( pops; an uppercase letter ends an atom name — add top × number to its count. Sort the names at the end.

How to solve Number of Atoms

Scan the formula backwards. Then every count is met before what it multiplies, so a stack of cumulative multipliers gives each atom's factor directly — no recursion needed.

Approach

  1. Keep a stack of multipliers starting with [1], a pending number num (built digit by digit from the right), and a map from atom name to count.
  2. Digit: prepend it to num.
  3. ): push top × (num or 1) and clear num. (: pop.
  4. Uppercase letter at i: the atom name runs from i through the lowercase letters after it. Add top × (num or 1) to its count and clear num. Lowercase letters themselves are skipped — they are read with their uppercase letter.
  5. Sort the names and write each with its count when the count exceeds 1.

Why it works

Right to left, an atom's own count is the number just read, and the groups enclosing it are exactly those whose ) has been seen but whose ( has not — the ones on the stack. Each stack entry already holds the product of all enclosing group counts, so the top is the total multiplier.

Complexity

  • Time — O(n + k log k) for k distinct atoms
  • Space — O(n)

Pitfalls

  • Counts can have several digits — when scanning backwards, build them with a place value, not by appending.
  • A missing count means 1, both for atoms and for groups.
  • Sort by character code: C comes before Ca, and every uppercase letter before every lowercase one.

Reference solution

Python

def countOfAtoms(formula: str) -> str:
    n = len(formula)
    counts = {}
    mult = [1]
    num = 0
    place = 1
    for i in range(n - 1, -1, -1):
        c = formula[i]
        if c.isdigit():
            num += (ord(c) - 48) * place
            place *= 10
        elif c == ')':
            mult.append(mult[-1] * (num if place > 1 else 1))
            num, place = 0, 1
        elif c == '(':
            mult.pop()
        elif c.isupper():
            j = i + 1
            while j < n and formula[j].islower():
                j += 1
            name = formula[i:j]
            counts[name] = counts.get(name, 0) + mult[-1] * (num if place > 1 else 1)
            num, place = 0, 1
    return ''.join(name + (str(counts[name]) if counts[name] > 1 else '') for name in sorted(counts))

Java

public static String countOfAtoms(String formula) {
    int n = formula.length();
    TreeMap<String, Long> counts = new TreeMap<>();
    long[] mult = new long[n + 2];
    int top = 0;
    mult[top++] = 1;
    long num = 0, place = 1;
    for (int i = n - 1; i >= 0; i--) {
        char c = formula.charAt(i);
        if (c >= '0' && c <= '9') {
            num += (c - '0') * place;
            place *= 10;
        } else if (c == ')') {
            mult[top] = mult[top - 1] * (place > 1 ? num : 1);
            top++;
            num = 0;
            place = 1;
        } else if (c == '(') {
            top--;
        } else if (c >= 'A' && c <= 'Z') {
            int j = i + 1;
            while (j < n && formula.charAt(j) >= 'a' && formula.charAt(j) <= 'z') j++;
            String name = formula.substring(i, j);
            counts.merge(name, mult[top - 1] * (place > 1 ? num : 1), Long::sum);
            num = 0;
            place = 1;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (Map.Entry<String, Long> e : counts.entrySet()) {
        sb.append(e.getKey());
        if (e.getValue() > 1) sb.append(e.getValue());
    }
    return sb.toString();
}

C++

string countOfAtoms(string formula) {
    int n = formula.size();
    map<string, long long> counts;
    vector<long long> mult(1, 1);
    long long num = 0, place = 1;
    for (int i = n - 1; i >= 0; i--) {
        char c = formula[i];
        if (c >= '0' && c <= '9') {
            num += (c - '0') * place;
            place *= 10;
        } else if (c == ')') {
            mult.push_back(mult.back() * (place > 1 ? num : 1));
            num = 0;
            place = 1;
        } else if (c == '(') {
            mult.pop_back();
        } else if (c >= 'A' && c <= 'Z') {
            int j = i + 1;
            while (j < n && formula[j] >= 'a' && formula[j] <= 'z') j++;
            counts[formula.substr(i, j - i)] += mult.back() * (place > 1 ? num : 1);
            num = 0;
            place = 1;
        }
    }
    string out;
    for (auto& e : counts) {
        out += e.first;
        if (e.second > 1) out += to_string(e.second);
    }
    return out;
}

JavaScript

var countOfAtoms = function(formula) {
    var n = formula.length;
    var counts = new Map();
    var mult = [1];
    var num = 0, place = 1;
    for (var i = n - 1; i >= 0; i--) {
        var c = formula[i];
        if (c >= "0" && c <= "9") {
            num += (c.charCodeAt(0) - 48) * place;
            place *= 10;
        } else if (c === ")") {
            mult.push(mult[mult.length - 1] * (place > 1 ? num : 1));
            num = 0;
            place = 1;
        } else if (c === "(") {
            mult.pop();
        } else if (c >= "A" && c <= "Z") {
            var j = i + 1;
            while (j < n && formula[j] >= "a" && formula[j] <= "z") j++;
            var name = formula.slice(i, j);
            var add = mult[mult.length - 1] * (place > 1 ? num : 1);
            counts.set(name, (counts.get(name) || 0) + add);
            num = 0;
            place = 1;
        }
    }
    var names = Array.from(counts.keys()).sort();
    var out = "";
    for (var k = 0; k < names.length; k++) {
        var cnt = counts.get(names[k]);
        out += names[k] + (cnt > 1 ? String(cnt) : "");
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets