NeetCode #381LC-726HardStack
← Back to All Problems#381 · #726 · Number of Atoms(原子的数量)
📌 Problem Statement & Constraints
Given a chemical
formula, return the count of each atom as a string in the form Name followed by its count (omitted when the count is 1), with names sorted alphabetically. Atoms start with an uppercase letter and may continue with lowercase letters; parentheses may be nested and followed by a multiplier. Constraints: 1 <= formula.length <= 1000.💡 Core Algorithmic Approaches
- Use a stack of counters, one per parenthesis level, with the outermost level as the base.
- Parsing: an uppercase letter starts an atom name; subsequent lowercase letters extend it; a following digit run is its count (default 1).
- On
(, push a new counter. On), read the multiplier, pop the counter, and merge it into the enclosing counter scaled by the multiplier. - Finally, emit the atoms of the base counter in sorted order, omitting counts of 1.
💻 Benchmark Python3 Implementation
class Solution:
def countOfAtoms(self, formula: str) -> str:
from collections import Counter
st = [Counter()] # one counter per nesting level
i, n = 0, len(formula)
while i < n:
ch = formula[i]
if ch == "(":
st.append(Counter())
i += 1
elif ch == ")":
i += 1
j = i
while j < n and formula[j].isdigit():
j += 1
mult = int(formula[i:j]) if j > i else 1
i = j
inner = st.pop()
for atom, cnt in inner.items():
st[-1][atom] += cnt * mult # scale by the multiplier
else:
j = i + 1
while j < n and formula[j].islower(): # extend the name
j += 1
atom = formula[i:j]
i = j
j = i
while j < n and formula[j].isdigit():
j += 1
cnt = int(formula[i:j]) if j > i else 1
i = j
st[-1][atom] += cnt
res = st[0]
return "".join(a + (str(res[a]) if res[a] > 1 else "") for a in sorted(res))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + k log k) where k is the number of distinct atoms: parsing is linear and the final sort is over the distinct atoms.
💾 Space Complexity
O(d + k) for the stack and the counters, where d is the nesting depth.
⚠️ Interview Pitfalls & Follow-ups
- Not extending atom names past the first letter:
Mgis one atom, so the lowercase scan is required. - Forgetting the multiplier after
): a parenthesised group can be followed by a count. - Treating a missing count as 0: the default is 1.
- Merging without scaling: the inner counts must be multiplied before being added to the parent.
- Sorting case-sensitively incorrectly: Python's default string sort gives the required order (all uppercase letters, then lowercase within a name).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.