Leetcode# 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 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].

How do we approach this problem?

IMHO, this problem is not hard but it is tricky to get the code right and additionally — it is trickier to write clean code. Here is the list of thoughts when I saw this problem:

Get Kunal Sinha’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Here are the thoughts that went through my mind when I first saw it:

1. Process character by character
   We read the string one character at a time, and based on what we encounter (digit, letter, [ or ]), we make decisions. Sometimes, we also need to revisit what we’ve already saved. That clearly suggests a good use case for a stack.
2. Separate stacks for numbers and strings
   Since the string contains both numbers and subsequences, it’s cleaner to keep numbers in their own stack. That way, I don’t need to unwind a mixed stack just to find the right repeat count.
3. String-based stack, not char-based
   Instead of pushing raw characters, it’s better to work with substrings. Why? Because when we build part of a string, we might need to push it back for later — especially with nested structures.
   For example, in "3[ab2[e]]", we first need to save "ab", then process the "2[e]" into "ee", and finally restore "ab" to build "abeeabeeabee".
4. The core intuition
   My guiding idea was: read characters one by one, and when I hit a ], I pop from the stack, expand the substring with its repeat count, and push it back.

Code snippets with explanation

Handling a number

Remember that a number may contain more than one digit so you need to iterate through every digit.

else if (Character.isDigit(c)) {
    // iterate until we have the entire number with us.
    int number=0;
    while (i < s.length() && Character.isDigit(s.charAt(i))) {
        number = 10* number + (s.charAt(i)-'0');
        i++;                    
    }
    stack_num.push(number);
    i--; // my current is pointing to beyond digit so decrementing it.
} 

Handling ‘]’

When we find a ‘]’, we have completed reading a string that needs to be repeated. So we need to read everything until ‘[‘ and then repeat the string and push it back to the stack.

else {
      // need to pop
      StringBuilder poppedBuilder = new StringBuilder();
      while (!stack_str.peek().equals("[")) {
          poppedBuilder.insert(0,stack_str.pop());
      }
      stack_str.pop(); // we need to remove the processed '['. May be there is a better way.                
      // pop the number from stack_nums and then repeat it those times.
      int count = stack_num.pop();
      String resultString = poppedBuilder.toString().repeat(count);
      // add it back to the stack.
      stack_str.push(resultString);
  }

Final Code

public String decodeString(String s) {
        Stack<Integer> stack_num = new Stack<>();
        Stack<String> stack_str = new Stack<>();
        
        int i=0;
        //"3[a2[c]]"
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == '[' || Character.isLetter(c)) {
                // If we find a '[' or a letter, push it into the stack as string.
                stack_str.push(String.valueOf(c));
            } else if (Character.isDigit(c)) {
                // iterate until we have the entire number with us.
                int number=0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    number = 10* number + (s.charAt(i)-'0');
                    i++;                    
                }
                stack_num.push(number);
                i--; // my current is pointing to beyond digit so decrementing it.
            } else {
                // need to pop
                StringBuilder poppedBuilder = new StringBuilder();
                while (!stack_str.peek().equals("[")) {
                    poppedBuilder.insert(0,stack_str.pop());
                }
                stack_str.pop(); // we need to remove the processed '['. May be there is a better way.                
                // pop the number from stack_nums and then repeat it those times.
                int count = stack_num.pop();
                String resultString = poppedBuilder.toString().repeat(count);
                // add it back to the stack.
                stack_str.push(resultString);
            }
            i++;
        }


        StringBuilder builder = new StringBuilder();
        while (!stack_str.isEmpty()) {
            builder.insert(0,stack_str.pop());  // This gets them in reverse order
        }
        return builder.toString(); 
    }

Alternate technique

While my original solution works fine, I came across another approach that’s worth mentioning. This one is arguably cleaner, though it may feel less intuitive at first because it requires careful resetting of state at the right times.

Here’s the outline:

1. Iterate one character at a time
   Just like before, we process the string sequentially. But unlike my first solution, we don’t run an inner loop to gather the full number or substring. Instead, we maintain state variables (like num and currentString) across iterations.
2. Build strings directly
   We continuously append characters to a currentString. There’s no need to pop multiple times and rebuild with a separate StringBuilder as in the earlier approach.
3. On encountering ]
   We pop from the stacks, repeat the decoded string, and then append it back to the current string — steadily moving toward the final result.
4. On encountering [
   This is the critical point. We:

• push the current string onto the stack,
• push the current number onto the stack,
• reset both currentString and num.
  These resets are what make this technique work cleanly.

Code

  public String decodeString(String s) {
        Stack<Integer> stack_num = new Stack<>();
        Deque<String> deque = new LinkedList<>();
        String current = "";
        int num=0;
        for(char c : s.toCharArray()) {
            if (c == '[') {
                stack_num.push(num);
                deque.addLast(current);
                num = 0;                
                current = "";
            } else if (Character.isDigit(c)) {
                num = num*10 + (c-'0');
            } else if (Character.isLetter(c)) {
                current += c;
            } else {
                // we have ']' we need to repeat and push it to the stack.
                int repeat = stack_num.pop();
                String prev = deque.removeLast();
                current = prev + current.repeat(repeat);
            }  
        }
        return current;
    }

Feel free to pick what suits you the most. I like the second approach but I took a bit of time to digest that technique but it does seem to be useful for writing clean code.

The time complexity is O(n)