Decode String

String, Stack Approach

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 will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

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"

Constraints:

• 1 <= s.length <= 30

• s consists of lowercase English letters, digits, and square brackets '[]'.

• s is guaranteed to be a valid input.

• All the integers in s are in the range [1, 300].

Solutions

This problem is a classic example of a problem that can be solved using a stack data structure. Here’s a step-by-step approach:

1. Initialize an empty stack: We’ll use this to keep track of the strings we need to repeat and the number of times we need to repeat them.

2. Iterate over the input string: We’ll look at each character one by one.

3. When we encounter a number, we know that it represents the number of times the following string should be repeated. We push this number onto our stack.

4. When we encounter an opening bracket ‘[’, this indicates the start of the string to be repeated. We push this onto our stack to mark the beginning of this string.

5. When we encounter a letter, we add it to the top of our stack (which should always be a string).

6. When we encounter a closing bracket ‘]’, this indicates the end of the current repeated string. We pop elements from our stack until we reach an opening bracket, concatenating these letters together to form our repeated string. We then pop the opening bracket and the number preceding it from our stack, and add the repeated string to our stack that many times.

7. At the end of our input string, our stack should contain one element: the decoded string. We return this as our result.

This approach works because the stack allows us to handle the nested structure of the input string, ensuring that we always repeat the correct strings the correct number of times. It’s a bit like peeling an onion: we handle the outermost layer first, then the next layer, and so on, until we reach the core.

Steps

public class Solution {
public string DecodeString(string s) {
    var stack = new Stack<string>();
    stack.Push("");
    
    int num = 0;
    foreach (char c in s) {
        if (char.IsDigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '[') {
            stack.Push(num.ToString());
            stack.Push("");
            num = 0;
        } else if (c == ']') {
            string str = stack.Pop();
            int count = Int32.Parse(stack.Pop());
            var sb = new StringBuilder(stack.Pop());
            for (int i = 0; i < count; i++) {
                sb.Append(str);
            }
            stack.Push(sb.ToString());
        } else {
            stack.Push(stack.Pop() + c);
        }
    }
    return stack.Pop();
 }
}

Complexity

• Time Complexity: O(1)

• Auxiliary Space: O(1)