Scale Engineer

Decode String

Med
#0381Time: 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: 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.29 companies
Patterns
Recursion
Data structures
StringStack
Companies
AgodaByteDanceCiscoGoldman Sachs

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem