Decode String

394.Decode String

String

Stack

Recursion

Problem Statement:

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.

Example:

Input:

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

→

Output:

"aaabcbc"

Java Solution:

public String decodeString(String s) {
    String res = "";  // Current result string
    Stack<Integer> countStack = new Stack<>();
    Stack resStack = new Stack<>();
    int idx = 0;
    int count = 0;

    while (idx < s.length()) {
        if (Character.isDigit(s.charAt(idx))) {
            count = 10 * count + (s.charAt(idx) - '0');  // Build multi-digit number
            
        } else if (s.charAt(idx) == '[') {
            countStack.push(count);  // Save number for later
            count = 0;
            
            resStack.push(res);  // Save current string
            res = "";
        }
        else if (s.charAt(idx) == ']') {
            StringBuilder temp = new StringBuilder(resStack.pop());
            int repeatTimes = countStack.pop();

            for (int i = 0; i < repeatTimes; i++)  // Repeat current string
                temp.append(res);
            
            res = temp.toString();
        }
        else {
            res += s.charAt(idx);  // Add regular characters
        }
        
        idx++;
    }
    return res;
}

Complexity:

Time: O(maxK * n) where maxK is the max value of k and n is the length of string
Space: O(m) where m is the number of nested brackets