Start learning free

LESSON 297 OF 344 · STACK

Decode String in Java: Using a List as a Stack of Buffers

Practice O(n) Read the full explanation

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.


Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

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].

STEP 1 OF 17
    Ctrl + Enter to check

    JAVA · STACK

    Decode String in Java, explained

    Problem overview

    The method decodeString receives an encoded string s and returns the decoded one. The only rule is k[encoded_string]: the text inside the brackets is repeated exactly k times. Brackets can be nested, text can sit before, between and after the groups, and the input is always well formed. Digits only ever appear as repeat counts, and a count can have several digits, such as 10[x].

    Take s = "3[a2[c]]". The inner group 2[c] becomes cc, so the outer group is 3[acc], which becomes accaccacc. For "2[abc]3[cd]ef" the groups sit side by side and the answer is abcabccdcdcdef, with ef copied unchanged at the end.

    Approach: finish the innermost group first

    In 3[a2[c]] the outer group can't be repeated until its content is fully decoded, and that content contains another group. So the work is naturally last in, first out: the group opened most recently is the first one closed. That is the job of a stack.

    The lesson keeps one stack of strings. Two kinds of entries live on it: numbers (a repeat count waiting for its bracket to close) and text buffers (the text decoded so far at one nesting level). Reading the string left to right:

    • a letter extends the buffer on top;
    • a digit starts a number entry or extends the number on top;
    • an opening bracket starts a fresh, empty buffer;
    • a closing bracket pops the finished buffer and its number, repeats the text, and appends the result to the entry below.

    Each character is handled once, so there is no repeated scanning. The cost is dominated by building the output text.

    Step by step

    1. Create the stack as a List<String> backed by an ArrayList. The end of the list is the top of the stack.
    2. Loop over the characters with s.toCharArray(), which gives a char[] that a for-each loop can walk.
    3. Opening bracket: push an empty string. Everything decoded inside this pair of brackets will collect there.
    4. Letter: check with Character.isLetter(c). If the stack is empty, which happens for text before any bracket, push an empty buffer first. Then replace the top entry with itself plus c.
    5. Digit: look at the top entry, or use an empty string when the stack is empty. If the top is not made only of digits, this digit starts a new number entry. Otherwise it continues a multi-digit count, so the top is replaced by itself plus the digit.
    6. Closing bracket (the final else): pop the text, then pop the count and parse it with Integer.parseInt.
    7. Repeat and fold back: currStr.repeat(currNum) builds the repeated text. If the stack is now empty, the result becomes the new bottom buffer. Otherwise it is appended to the buffer below, which is the level that contained this group.
    8. Return the last entry. For valid input, exactly one buffer is left, holding the whole answer.

    The solution in Java

    class Solution {
    public String decodeString(String s) {
        List<String> stack = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (c == '[') {
                stack.add("");
            } else if (Character.isLetter(c)) {
                if (stack.isEmpty()) {
                    stack.add("");
                }
                stack.set(stack.size() - 1, stack.get(stack.size() - 1) + c);
            } else if (Character.isDigit(c)) {
                String top = stack.isEmpty() ? "" : stack.get(stack.size() - 1);
                if (!top.matches("\\d+")) {
                    stack.add(String.valueOf(c));
                } else {
                    stack.set(stack.size() - 1, top + c);
                }
            } else {
                String currStr = stack.remove(stack.size() - 1);
                int currNum = Integer.parseInt(stack.remove(stack.size() - 1));
                String repeated = currStr.repeat(currNum);
                if (stack.isEmpty()) {
                    stack.add(repeated);
                } else {
                    stack.set(stack.size() - 1, stack.get(stack.size() - 1) + repeated);
                }
            }
        }
        return stack.get(stack.size() - 1);
    }
}

    Here is how the stack looks while 3[a2[c]] is processed:

    after 3    ["3"]
after [    ["3", ""]
after a    ["3", "a"]
after 2    ["3", "a", "2"]
after [    ["3", "a", "2", ""]
after c    ["3", "a", "2", "c"]
after ]    ["3", "acc"]
after ]    ["accaccacc"]

    Java details worth a closer look:

    • Strings are immutable. stack.get(i) + c builds a new string, so the result must be written back with stack.set. Calling get and concatenating alone would change nothing.
    • String + char. Concatenating a char onto a String appends the character itself. Adding a char to an int would do arithmetic instead, which is why the digits are kept as text and only parsed at the end.
    • matches("\\d+"). The string literal "\\d+" holds the regular expression \d+, meaning one or more digits. It must match the entire string, and an empty string doesn't match, so an empty buffer on top is never mistaken for a number.
    • remove(int) on a list. stack.remove(stack.size() - 1) removes by index and returns the removed element, so it pops and reads in one call. Because the argument is an int, Java picks the index version, not remove(Object).
    • String.repeat exists since Java 11. "ab".repeat(3) is "ababab", and a count of zero gives an empty string.
    • The final else handles ']' only because the input is guaranteed to hold nothing but lowercase letters, digits and brackets.

    Complexity

    Let L be the length of the decoded output. Time: O(L) plus the work of reading s. Each closing bracket builds a repeated string and then copies it into the buffer below, and a result can be copied again by every enclosing group. The tests keep the output at most 100,000 characters, so this stays small. The copying could be heavier for deeply nested groups of long text, which is the price of using immutable strings.

    Space: O(L). The stack holds at most the partial text at each nesting level, and no entry is longer than the final output.

    Edge cases and common mistakes

    • Multi-digit counts. 10[x] must give ten copies. Treating each digit as its own count would try to parse 1 and 0 separately.
    • Text before the first bracket. In ab3[c] the letters arrive with an empty stack. Without the lazy push, stack.get(stack.size() - 1) would throw on index -1. The answer is abccc.
    • Text after a group. In 2[abc]3[cd]ef the ef joins the buffer that the first two groups were folded into.
    • Nested groups with text on both sides. 2[3[a]b] gives aaabaaab: the inner group is folded into the outer buffer before b is appended.
    • No brackets at all. abc returns abc.
    • Parsing the count too early. Calling Integer.parseInt on a partial number would produce the wrong count for numbers like 23. The number is complete only when its bracket closes.

    Testing

    • "3[a]2[bc]" gives "aaabcbc".
    • "3[a2[c]]" gives "accaccacc".
    • "2[abc]3[cd]ef" gives "abcabccdcdcdef".
    • "ab3[c]" gives "abccc".
    • "2[3[a]b]" gives "aaabaaab".
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free