0415HardHash TableStringStackSorting

Flat-Pack Parts Tally

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A furniture workshop writes the contents of a flat-pack kit in a compact notation, given to you as formula.

A part code is one capital letter followed by zero or more small letters, such as "K", "Nut" or "Bba".
A part code standing on its own means one of that part. A part code followed immediately by a whole number means that many of it, so "Nut2" means two nuts.
Any run of the notation may be wrapped in round brackets. A bracketed run followed by a whole number means the entire run is packed that many times, so "(BoltNut)3" packs three bolts and three nuts. A bracketed run with no number after it is packed once.
Bracketed runs may sit inside other bracketed runs, and the numbers multiply through.

Write the kit's total contents in the workshop's tidy form: every distinct part code exactly once, the codes in dictionary order, and each code followed immediately by its total quantity. A quantity of exactly one is left off, so a kit holding one hinge and five screws is written "HingeScrew5".

Return the tidy form of formula as a string. Every number written in the notation is at least 2 and carries no leading zero, and formula is always well formed.

Examples

Example 1

Input: formula = "(BoltNut)3Washer"
Output: "Bolt3Nut3Washer"

The bracketed run is packed three times, giving three bolts and three nuts, and one washer follows it. In dictionary order the codes are Bolt, Nut, Washer, and the washer's quantity of one is left off.

Example 2

Input: formula = "((Cam2Pin)3Rod)2"
Output: "Cam12Pin6Rod2"

The inner run holds two cams and one pin and is packed three times, so six cams and three pins, joined by one rod. All of that is packed twice, giving twelve cams, six pins and two rods.

Example 3

Input: formula = "BAb2"
Output: "Ab2B"

The notation names one B and two Ab. Dictionary order puts Ab before B, and B's quantity of one is left off.

Example 4

Input: formula = "(Ab2)12"
Output: "Ab24"

Two Ab sit inside the brackets and the run is packed twelve times, so the kit holds twenty-four of them.

Example 5

Input: formula = "K"
Output: "K"

A single part code with no number and no brackets, so the kit holds one K and the quantity is left off.

Constraints

1 <= formula.length <= 1000
formula consists of English letters, digits, '(' and ')'.
formula is always a well formed kit notation.
Every number appearing in formula is at least 2 and has no leading zero.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_of_atoms(formula: str) -> str:

Java

public String countOfAtoms(String formula)

The intended approach

Time O(n*d + k log k) for a notation of length n nested d deep with k distinct part codes: each character is read once and each close bracket folds at most k tallies up one level, which is O(n^2) in the worst case, plus one sort of the codes.Space O(n) for the stack of tallies, whose live entries are bounded by the number of part codes written in the notation, plus the returned string.

Sweep the notation once, keeping a stack of tallies with one tally per bracketed run that is currently open. A part code and its optional number go into the tally on top. An opening bracket pushes an empty tally. A closing bracket reads the number that follows, scales every quantity in the tally on top by it, and adds those quantities into the tally underneath, then drops the top one. Numbers are accumulated digit by digit so a multi-digit count is read whole. When the sweep ends the bottom tally holds the kit, and sorting its codes gives the tidy form. An explicit stack rather than nested calls keeps deeply bracketed notations safe.

Pythonentry point: count_of_atoms

def count_of_atoms(formula):
    # One left-to-right scan with a stack of tallies, one tally per open
    # section. A close bracket reads the repeat count that follows it, scales
    # the section's tally and folds it into the section outside. Iterative, so
    # 500 nested sections are safe.
    size = len(formula)
    stack = [{}]
    pos = 0
    while pos < size:
        ch = formula[pos]
        if ch == "(":
            stack.append({})
            pos += 1
        elif ch == ")":
            pos += 1
            times = 0
            digits = 0
            while pos < size and formula[pos].isdigit():
                times = times * 10 + (ord(formula[pos]) - 48)
                digits += 1
                pos += 1
            if digits == 0:
                times = 1
            inner = stack.pop()
            outer = stack[-1]
            for code, many in inner.items():
                outer[code] = outer.get(code, 0) + many * times
        else:
            start = pos
            pos += 1
            while pos < size and formula[pos].islower():
                pos += 1
            code = formula[start:pos]
            times = 0
            digits = 0
            while pos < size and formula[pos].isdigit():
                times = times * 10 + (ord(formula[pos]) - 48)
                digits += 1
                pos += 1
            if digits == 0:
                times = 1
            tally = stack[-1]
            tally[code] = tally.get(code, 0) + times
    tally = stack[0]
    pieces = []
    for code in sorted(tally):
        pieces.append(code)
        if tally[code] > 1:
            pieces.append(str(tally[code]))
    return "".join(pieces)

The obvious version

Flatten the notation textually: repeatedly find the innermost bracketed run, replace it with its own text repeated the stated number of times, and drop the brackets. Once no brackets remain, walk the flat text and add up each part code's quantities, then emit the codes in dictionary order.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_of_atoms(formula):
    text = formula
    while "(" in text:
        open_at = text.rfind("(")
        close_at = text.index(")", open_at)
        inside = text[open_at + 1:close_at]
        after = close_at + 1
        digits = ""
        while after < len(text) and text[after].isdigit():
            digits += text[after]
            after += 1
        times = int(digits) if digits else 1
        text = text[:open_at] + inside * times + text[after:]
    tally = {}
    pos = 0
    while pos < len(text):
        start = pos
        pos += 1
        while pos < len(text) and text[pos].islower():
            pos += 1
        code = text[start:pos]
        digits = ""
        while pos < len(text) and text[pos].isdigit():
            digits += text[pos]
            pos += 1
        tally[code] = tally.get(code, 0) + (int(digits) if digits else 1)
    pieces = []
    for code in sorted(tally):
        pieces.append(code)
        if tally[code] > 1:
            pieces.append(str(tally[code]))
    return "".join(pieces)

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in