Decode the string

JavaView on GFG

Intuition

Decode run-length encoded string like "3[b2[ca]]". Stack-based decoding for nested encodings.

Algorithm

1Use two stacks: one for strings, one for numbers.
2On digit: build number. On "[": push current string and number. On "]": repeat top string by top number, append to previous.

Common Pitfalls

•Same as LC 394. Handle multi-digit numbers. Build current string char by char between brackets.

Decode the string.java

Java

// Approach: Stack-based decoding. Push characters/counts; on ']' pop until '[' and repeat the inner string.
// Time: O(n * max_k) Space: O(n)
import java.util.*;

class Solution {
    static String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> stringStack = new Stack<>();
        String currentString = "";
        int k = 0;

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch))
                k = k * 10 + (ch - '0');
            else if (ch == '[') {
                countStack.push(k);
                stringStack.push(currentString);
                currentString = "";
                k = 0;
            } else if (ch == ']') {
                StringBuilder decodedString = new StringBuilder(stringStack.pop());
                int repeatTimes = countStack.pop();
                for (int i = 0; i < repeatTimes; i++)
                    decodedString.append(currentString);

                currentString = decodedString.toString();
            } else
                currentString += ch;
        }

        return currentString;
    }
}

Was this solution helpful?