394. Decode String

📝 Problem Details

• Title: 394. Decode String
• Link: https://leetcode.com/problems/decode-string/
• Difficulty: Medium
• Tags/Categories: Strings Stack

given an encoded string s, return its decoded string encoding rule: k[encoded_string] repeat encoded_string k times k is guaranteed to be a positive integer

💭What Were My Initial Thoughts?

- Iterate through the string
- When encountering a square bracket [], 
    - Get the multiplier which is the character before the opening bracket
    - Extract the substring within the brackets
    - Repeat it accordingly and append to result string

Why This Approach Fails:

• It assumes that the multiplier is always a single-digit number immediately before the [. This doesn’t handle multi-digit numbers like "10[a]".
• It doesn’t account for nested structures, like "3[a2[c]]" — where you must decode the inner substring first, before the outer one.
• Without a stack or recursion, it’s hard to track context between different layers of brackets.

💡 Explanation of Solution

- use one stack to hold characters as you iterate through the string
- push everything onto the stack until you hit the closing bracket ]
- when you hit [
	- pop characters to build the substring until you hit [
	- pop [ off the stack
	- then build the repeat count by popping digits from the stack
	- expand the decoded string and push it back onto the stack, char by char
- at the end, the stack contains the fully decoded string

For input 3[a2[c]]

Iteration builds:
- push '3'
- push '['
- push 'a'
- push '2'
- push '['
- push 'c'
- hit ']': pop 'c' → repeat 2 times → "cc"
- push back: ..., '[', 'a', 'c', 'c'
- hit ']': pop 'c', 'c', 'a' → repeat 3 times → "accaccacc"

⌛ Complexity Analysis

Time Complexity: O(n * k)
- where n is the length of the string
- k is the max repetition count
- Each character is processed once, and repeated strings take time proportional to their length

Space Complexity: O(n)
- for use of the stack

💻 Implementation of Solution

class Solution {
public:
    string decodeString(string s) {
        stack<char> stk;
 
        for (char c : s) {
            if (c != ']') {
                stk.push(c);
            } else {
                // Step 1: Get the substring inside brackets
                string decoded = "";
                while (!stk.empty() && stk.top() != '[') {
                    decoded = stk.top() + decoded;
                    stk.pop();
                }
 
                stk.pop(); // remove the '['
 
                // Step 2: Get the number (could be multiple digits)
                string kStr = "";
                while (!stk.empty() && isdigit(stk.top())) {
                    kStr = stk.top() + kStr;
                    stk.pop();
                }
 
                int k = stoi(kStr);
 
                // Step 3: Repeat the decoded string and push back to stack
                for (int i = 0; i < k; ++i) {
                    for (char ch : decoded) {
                        stk.push(ch);
                    }
                }
            }
        }
 
        // Final step: pop everything to form result
        string result = "";
        while (!stk.empty()) {
            result = stk.top() + result;
            stk.pop();
        }
 
        return result;
    }
};