Decode String

MEDIUM

Description

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 10⁵.

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

Approaches

Checkout 3 different approaches to solve Decode String. Click on different approaches to view the approach and algorithm in detail.

Brute-Force with String Replacement

This approach repeatedly finds the innermost k[encoded_string] pattern, decodes it, and replaces it in the string. This process continues until no encoded patterns are left. It's a straightforward idea but suffers from poor performance due to expensive string operations in a loop.

Algorithm

Start a loop that continues as long as the string s contains the character [.
Inside the loop, find the index of the first ] character, let's call it right.
Find the index of the last [ character that appears before right, let's call it left. This ensures we are processing the innermost bracketed expression first.
Extract the encoded_string which is the substring between left + 1 and right.
Find the start of the number k by scanning backwards from left - 1 as long as the characters are digits.
Parse this number k.
Create the decoded part by repeating the encoded_string k times.
Construct a new string by replacing the k[encoded_string] part with the decoded part.
Repeat the loop with the modified string.
Once the loop finishes, return the fully decoded string.

The algorithm iterates as long as there are square brackets [ in the string. In each iteration, it locates the innermost pair of brackets. This can be done by finding the last occurrence of [ and the first occurrence of ] after it. Once the innermost encoded_string is identified, the corresponding repeat count k is parsed from the digits just before the [. The encoded_string is repeated k times to get the decoded part. Finally, the entire k[encoded_string] substring is replaced with the newly decoded part in the main string. This loop continues until the string is fully decoded.

class Solution {
    public String decodeString(String s) {
        while (s.indexOf('[') != -1) {
            int right = s.indexOf(']');
            int left = s.lastIndexOf('[', right);
            
            String encoded = s.substring(left + 1, right);
            
            int k_start = left - 1;
            while (k_start >= 0 && Character.isDigit(s.charAt(k_start))) {
                k_start--;
            }
            k_start++;
            
            int k = Integer.parseInt(s.substring(k_start, left));
            
            StringBuilder decoded = new StringBuilder();
            for (int i = 0; i < k; i++) {
                decoded.append(encoded);
            }
            
            s = s.substring(0, k_start) + decoded.toString() + s.substring(right + 1);
        }
        return s;
    }
}

Complexity Analysis

Time Complexity: O(N * M) or worse, where N is the number of bracket pairs and M is the length of the output string. In each step, we scan the string (which can grow up to length M) to find brackets. String concatenations and replacements are also expensive.Space Complexity: O(M), where M is the length of the output string. A new string of length up to M can be created in each iteration.

Pros and Cons

Pros:

Conceptually simple to understand.

Cons:

Very inefficient due to repeated string scanning and manipulation.
Creating new string objects in a loop is memory and time-intensive in languages like Java.
Will likely result in a 'Time Limit Exceeded' error for larger inputs.

Code Solutions

Checking out 2 solutions in different languages for Decode String. Click on different languages to view the code.

class Solution {
public
  String decodeString(String s) {
    Deque<Integer> s1 = new ArrayDeque<>();
    Deque<String> s2 = new ArrayDeque<>();
    int num = 0;
    String res = "";
    for (char c : s.toCharArray()) {
      if ('0' <= c && c <= '9') {
        num = num * 10 + c - '0';
      } else if (c == '[') {
        s1.push(num);
        s2.push(res);
        num = 0;
        res = "";
      } else if (c == ']') {
        StringBuilder t = new StringBuilder();
        for (int i = 0, n = s1.pop(); i < n; ++i) {
          t.append(res);
        }
        res = s2.pop() + t.toString();
      } else {
        res += String.valueOf(c);
      }
    }
    return res;
  }
}

Video Solution

Watch the video walkthrough for Decode String

Patterns:

Recursion

Data Structures:

StringStack

Companies:

Agoda |ByteDance |Cisco |Goldman Sachs |