Here is two solution for problem “Decode String”

1. Input, Output, Contraints

1. Input

A string s that encodes patterns like:

k[encoded_string]

where encoded_string inside the brackets is repeated exactly k times.

Nested encoding is allowed.

1. Output

Return the decoded string.

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”

1. Constraints

1 ≤ s.length ≤ 30,000

s consists of digits, letters, and brackets [].

Properly formed (no invalid brackets).

Numbers can have multiple digits, e.g., “10[a]”.

2. Intuition / How to Think About It

The encoding behaves like a stack of contexts:

• Every [ starts a new level of encoded substring.

• Every ] ends a level — we pop the substring and repeat it.

We’ll keep two stacks:

• num_stack: holds repeat counts

• str_stack: holds partial strings

At the end, current_str holds the decoded result.

3. Dry Run Example

Let’s dry run s = “3[a2[c]]”

Initialize:

num_stack = [] str_stack = [] cur_num = 0 cur_str = “”

Step-by-step

char	Action	num_stack	str_stack	cur_num	cur_str
'3'	digit → build number			3	""
'['	push (3, "")	[3]	[""]	0	""
'a'	letter → add to cur_str	[3]	[""]	0	"a"
'2'	digit → build number	[3]	[""]	2	"a"
'['	push (2, "a")	[3,2]	["","a"]	0	""
'c'	letter → cur_str += 'c'	[3,2]	["","a"]	0	"c"
']'	pop num=2, prev="a" → cur_str = "a" + "c"*2 = "acc"	[3]	[""]	0	"acc"
']'	pop num=3, prev="" → cur_str = "" + "acc"*3 = "accaccacc"	[]	[]	0	"accaccacc"

✅ Final: “accaccacc”

4. Implementation — Stack-based (O(N))

def decodeString(s: str) -> str:
    num_stack = []
    str_stack = []
    cur_num = 0
    cur_str = ""

    for ch in s:
        if ch.isdigit():
            cur_num = cur_num * 10 + int(ch)  # handle multi-digit numbers
        elif ch == '[':
            num_stack.append(cur_num)
            str_stack.append(cur_str)
            cur_num = 0
            cur_str = ""
        elif ch == ']':
            repeat = num_stack.pop()
            prev_str = str_stack.pop()
            cur_str = prev_str + cur_str * repeat
        else:
            cur_str += ch

    return cur_str

5. Time Complexity and Space Complexity

• Time Complexity: O(N).

• Space Complexity: O(N).