Sweaty Imposter

Decode String

MediumStackMidOpen on LeetCodeUpdated

You're given an encoded string s. The rule k[text] means text repeated exactly k times, where k is a positive integer that may have more than one digit. Encodings can be nested, as in 2[a3[b]], which decodes to "abbbabbb". Letters outside any brackets are copied as they are. Return the fully decoded string. The input is always well formed: digits appear only as repeat counts, and every count is followed by a bracketed section.

Examples

s = "3[a]2[bc]" returns "aaabcbc"

3[a] expands to "aaa" and 2[bc] to "bcbc". Joined in order they give "aaabcbc".

s = "3[a2[c]]" returns "accaccacc"

The inner 2[c] becomes "cc", so the outer section reads "acc". Three copies of it give "accaccacc".

s = "2[abc]10[x]ef" returns "abcabcxxxxxxxxxxef"

2[abc] gives "abcabc". The count 10 has two digits and gives ten x's, and "ef" sits outside any brackets, so it is copied once.

Constraints

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets '[]'.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].
  • The length of the output will never exceed 10^5.

Hints

Hint 1

Each ']' finishes the innermost section that is still open. When a section finishes, what do you need to know to expand it and attach it to the text around it?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Sections resolve innermost first, so keep a stack of what was pending when each '[' opened: the text built before it and its repeat count. Letters append to the current string, and digits accumulate a possibly multi-digit count. At '[' push (current, k) and start fresh; at ']' pop and set current = previous + current repeated count times. With m the decoded length and d the deepest nesting, each output character is copied at most once per level: O(n + m * d) time and O(m) space.

Time

O(n + m * d)

Space

O(m)

Pitfall

Reading the repeat count as a single digit, so 12[a] turns into a stray 1 followed by 2[a]. Accumulate k = k * 10 + digit, and reset k to 0 once you push it at '['.

Solutions

class Solution {
    public String decodeString(String s) {
        Deque<Integer> counts = new ArrayDeque<>();
        Deque<StringBuilder> outer = new ArrayDeque<>();
        StringBuilder current = new StringBuilder();
        int k = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                counts.push(k);
                outer.push(current);
                current = new StringBuilder();
                k = 0;
            } else if (c == ']') {
                StringBuilder decoded = outer.pop();
                decoded.append(current.toString().repeat(counts.pop()));
                current = decoded;
            } else {
                current.append(c);
            }
        }
        return current.toString();
    }
}
Drill This