[Medium] 394. Decode String

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 won’t be input like 3a or 2[4].

Examples

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Explanation: 
- "3[a]" decodes to "aaa"
- "2[bc]" decodes to "bcbc"
- Combined: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"
Explanation: 
- "3[a2[c]]" decodes to "accaccacc"
- Inner "2[c]" decodes to "cc"
- Outer "3[a...]" decodes to "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Explanation: 
- "2[abc]" decodes to "abcabc"
- "3[cd]" decodes to "cdcdcd"
- "ef" remains as "ef"
- Combined: "abcabccdcdcdef"

Constraints

1 <= s.length <= 30
s consists of lowercase English letters, digits, and square brackets '[' and ']'.
s is a valid encoded string, that is always possible to decode.
All the integers in s are in the range [1, 300].

Thinking Process

Two stacks: One for counts, one for strings
Current string: Maintains the string being built

Stack matches nested or LIFO structure (parentheses, monotonic scans).
Push on open / larger; pop when the current element resolves pending work.
Monotonic stack finds next greater/smaller in O(n).

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Monotonic stack (this problem)	O(n)	O(n)	Next greater/smaller element
Parentheses matching	O(n)	O(n)	Push open, pop on close
Expression evaluation	O(n)	O(n)	Operand + operator stacks
Stack simulation	O(n)	O(n)	Process in LIFO order

Solution

Time Complexity: O(n) where n is the length of the decoded string
Space Complexity: O(n) for the stack and result string

Use two stacks to handle nested encoded strings: one for counts and one for strings.

// import java.util.*;
class Solution {
        public String decodeString(String s) {
        Deque<Integer> counts = new ArrayDeque<>();
        Deque<String> strings = new ArrayDeque<>();
        String curr;
        int k = 0;

        for (int ch : s) {
            if(isdigit(ch)) {
                k = k 10 + ch - '0';
            } else if(ch == '[') {
                counts.offer(k);
                strings.offer(curr);
                curr = "";
                k = 0;
            } else if(ch == ']') {
                String decode = strings.peek();
                strings.poll();
                int count = counts.peek();
                while(count--) decode += curr;
                counts.poll();
                curr = decode;
            } else {
                curr += ch;
            }
        }
        return curr;
    }
}

Solution Explanation

Key Insight: Use two stacks to handle nested encoded strings and maintain the current string being built.

Steps:

Process each character in the input string
For digits: Build the count number
For ‘[’: Push count and current string to stacks, reset for nested processing
For ‘]’: Pop from stacks, repeat current string, and update current string
For letters: Add to current string
Return final decoded string

Step-by-Step Example

Example: `s = "3[a2[c]]"`

Character	Action	Counts Stack	Strings Stack	Current String	Explanation
‘3’	Build count	[]	[]	””	k = 3
’[’	Push to stacks	[3]	[””]	””	Save state, reset
‘a’	Add to current	[3]	[””]	“a”	Add letter
‘2’	Build count	[3]	[””]	“a”	k = 2
’[’	Push to stacks	[3,2]	[””,”a”]	””	Save state, reset
‘c’	Add to current	[3,2]	[””,”a”]	“c”	Add letter
’]’	Decode	[3]	[””]	“cc”	Repeat “c” 2 times
’]’	Decode	[]	[]	“accaccacc”	Repeat “cc” 3 times

Final result: "accaccacc"

Algorithm Breakdown

Character Processing:

class Solution {
        public String decodeString(String s, int i) {
        String result;
        while(i < s.length() && s.charAt(i) != ']') {
            if(isdigit(s.charAt(i))) {
        int k = 0;
                while(i < s.length() && isdigit(s.charAt(i))) {
                    k = k 10 + s[i++] - '0';
                }
                i++; // skip '['
                String decoded = decodeString(s, i);
                i++; // skip ']'
                while(k--) result += decoded;
            } else {
                result += s[i++];
            }
        }
        return result;
    }
        public String decodeString(String s) {
        int i = 0;
        return decodeString = new return(s, i);
    }
}

Process:

Digit: Build multi-digit count
’[’: Save current state to stacks
’]’: Decode by repeating current string
Letter: Add to current string

Stack Operations:

Push Operation (on ‘[’):

// import java.util.*;
class Solution {
        public String decodeString(String s) {
        Deque<String> st = new ArrayDeque<>();
        String curr = "";
        int k = 0;

        for (char c : s.toCharArray()) {
            if(isdigit(c)) {
                k = k 10 + c - '0';
            } else if(c == '[') {
                st.offer(String.valueOf(k));
                st.offer(curr);
                curr = "";
                k = 0;
            } else if(c == ']') {
                String prev = st.peek(); st.poll();
                int count = Integer.parseInt(st.peek()); st.poll();
                String temp = "";
                for(int i = 0; i < count; i++) {
                    temp += curr;
                }
                curr = prev + temp;
            } else {
                curr += c;
            }
        }
        return curr;
    }
}

Pop Operation (on ‘]’):

string decode = strings.top();
strings.pop();
int count = counts.top();
while(count--) decode += curr;
counts.pop();
curr = decode;

Complexity

| Operation | Time Complexity | Space Complexity | |———–|—————-|——————| | Character processing | O(n) | O(n) | | Stack operations | O(n) | O(n) | | String concatenation | O(m) | O(m) | | Total | O(n + m) | O(n + m) |

Where n is the input length and m is the decoded string length.

Detailed Example Walkthrough

Example: `s = "2[abc]3[cd]ef"`

Character	Action	Counts Stack	Strings Stack	Current String	Explanation
‘2’	Build count	[]	[]	””	k = 2
’[’	Push to stacks	[2]	[””]	””	Save state
‘a’	Add to current	[2]	[””]	“a”	Add letter
‘b’	Add to current	[2]	[””]	“ab”	Add letter
‘c’	Add to current	[2]	[””]	“abc”	Add letter
’]’	Decode	[]	[]	“abcabc”	Repeat “abc” 2 times
‘3’	Build count	[]	[]	“abcabc”	k = 3
’[’	Push to stacks	[3]	[“abcabc”]	””	Save state
‘c’	Add to current	[3]	[“abcabc”]	“c”	Add letter
‘d’	Add to current	[3]	[“abcabc”]	“cd”	Add letter
’]’	Decode	[]	[]	“abcabccdcdcd”	Repeat “cd” 3 times
‘e’	Add to current	[]	[]	“abcabccdcdcde”	Add letter
‘f’	Add to current	[]	[]	“abcabccdcdcdef”	Add letter

Final result: "abcabccdcdcdef"

Common Mistakes

Single letter: s = "a" → "a"
Single repetition: s = "2[a]" → "aa"
No nesting: s = "3[a]2[b]" → "aaabb"
Deep nesting: s = "2[3[4[a]]]" → "aaaaaaaaaaaaaaaaaaaaaaaa"
Wrong count handling: Not building multi-digit numbers correctly
Stack order: Pushing/popping in wrong order
String concatenation: Not handling nested repetitions properly
Edge cases: Not handling single characters or no brackets

Why This Solution Works

Stack-Based Approach:

Two stacks: Efficiently handle nested structures
State preservation: Save current state when entering brackets
State restoration: Restore state when exiting brackets
Arbitrary nesting: Handle any level of nesting

String Processing:

Character by character: Process input incrementally
Count building: Handle multi-digit numbers
String repetition: Efficiently repeat strings
Memory efficient: Build result incrementally

Key Algorithm Properties:

Correctness: Always produces valid decoded string
Efficiency: O(n + m) time complexity
Simplicity: Easy to understand and implement
Scalability: Handles arbitrary nesting levels

References

LC 394: Decode String on LeetCode
LeetCode Discuss — LC 394: Decode String
LeetCode Editorial (may require premium)

Key Takeaways

Stack-Based Approach:

Two stacks: One for counts, one for strings
State preservation: Save current state when entering nested brackets
State restoration: Restore state when exiting nested brackets
Efficient processing: Handle arbitrary nesting levels

String Building:

Current string: Maintains the string being built
Repetition: Repeat current string by count
Concatenation: Build final result incrementally
Memory efficient: Process character by character

Robina Li

[Medium] 394. Decode String

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution Explanation

Step-by-Step Example

Example: `s = "3[a2[c]]"`

Algorithm Breakdown

Character Processing:

Stack Operations:

Complexity

Detailed Example Walkthrough

Example: `s = "2[abc]3[cd]ef"`

Common Mistakes

Why This Solution Works

Stack-Based Approach:

String Processing:

Key Algorithm Properties:

References

Key Takeaways

Stack-Based Approach:

String Building:

Related Posts

Recent Posts

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution Explanation

Step-by-Step Example

Example: s = "3[a2[c]]"

Algorithm Breakdown

Character Processing:

Stack Operations:

Complexity

Detailed Example Walkthrough

Example: s = "2[abc]3[cd]ef"

Common Mistakes

Related Problems

Why This Solution Works

Stack-Based Approach:

String Processing:

Key Algorithm Properties:

References

Key Takeaways

Stack-Based Approach:

String Building:

Related Posts

Recent Posts

Example: `s = "3[a2[c]]"`

Example: `s = "2[abc]3[cd]ef"`