Decode String
MedPrompt
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 <= 30sconsists of lowercase English letters, digits, and square brackets'[]'.sis guaranteed to be a valid input.- All the integers in
sare 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
scontains the character[. - Inside the loop, find the index of the first
]character, let's call itright. - Find the index of the last
[character that appears beforeright, let's call itleft. This ensures we are processing the innermost bracketed expression first. - Extract the
encoded_stringwhich is the substring betweenleft + 1andright. - Find the start of the number
kby scanning backwards fromleft - 1as long as the characters are digits. - Parse this number
k. - Create the decoded part by repeating the
encoded_stringktimes. - 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.
This approach treats the string as a nested structure and uses recursion to decode it. A global index is used to keep track of the current position in the string, simulating a parser that consumes the string as it goes. This is a form of depth-first traversal of the encoded structure.
Algorithm
- Define a recursive function, say
decode(), which will parse the strings. Use a global indexito track the position. - Initialize an empty
StringBuilderresultand acountto 0. - Loop while
iis within the bounds ofsand the character is not]. - If
s.charAt(i)is a digit, updatecount. - If
s.charAt(i)is[, incrementito skip it, then make a recursive call todecode(). Append the returned string toresultcounttimes. Resetcountto 0. - If
s.charAt(i)is a letter, append it toresult. - In all cases, increment
i. - When the loop terminates because
ireaches the end of the string or a]is found, if it was a], incrementito consume it. - Return
result.toString().
Walkthrough
The core of this approach is a recursive function that decodes a part of the string and returns the result. We use a global or class-level variable i to maintain the current parsing position across recursive calls. The function iterates through the string starting from the current position i. If it encounters a letter, it appends it to the result for the current level. If it encounters a digit, it parses the complete number to get the repetition count k. When [ is found, it means a new nested level begins. We make a recursive call to decode the content within the brackets. The result of the recursive call is then appended k times to the current level's result. When ] is found, it signifies the end of the current decoding scope, and the function returns the accumulated string for its level.
class Solution { private int i = 0; public String decodeString(String s) { StringBuilder result = new StringBuilder(); int count = 0; while (i < s.length()) { char c = s.charAt(i); if (Character.isDigit(c)) { count = count * 10 + (c - '0'); i++; } else if (c == '[') { i++; // Move past '[' String decodedSubstring = decodeString(s); // Recursive call for (int j = 0; j < count; j++) { result.append(decodedSubstring); } count = 0; // Reset count for the next number } else if (c == ']') { i++; // Move past ']' return result.toString(); // End of current scope } else { // It's a letter result.append(c); i++; } } return result.toString(); }}Complexity
Time
O(M), where M is the length of the decoded output string. We traverse each character of the input string once, and the string building operations take time proportional to the final length.
Space
O(M), where M is the length of the output string. The recursion call stack depth is at most the nesting level D, but the space for the result `StringBuilder` in each call contributes. The total space for all `StringBuilder`s at any point is bounded by O(M).
Trade-offs
Pros
Elegant and naturally models the problem's recursive structure.
Efficient in terms of time complexity.
Cons
Can lead to stack overflow for extremely deep nesting (though not an issue for the given constraints).
Managing state (the index
i) via a global or shared variable can sometimes be less clean than passing it explicitly.
This approach uses two stacks to iteratively decode the string, avoiding recursion. One stack stores the repetition counts (countStack), and the other stores the string being built before encountering a new nested scope (stringStack). This is generally the most robust and efficient method.
Algorithm
- Initialize a
countStackfor integers and astringStackforStringBuilders. - Initialize
currentString = new StringBuilder()andk = 0. - Iterate through each character
chof the input strings. - If
chis a digit, updatek:k = k * 10 + (ch - '0'). - If
chis[, pushktocountStack, pushcurrentStringtostringStack, and resetk = 0andcurrentString = new StringBuilder(). - If
chis], pop fromcountStackto getrepeatCountand pop fromstringStackto getpreviousString. AppendcurrentStringtopreviousStringrepeatCounttimes. UpdatecurrentStringto bepreviousString. - If
chis a letter, append it tocurrentString. - After the loop,
currentStringholds the final result.
Walkthrough
We iterate through the input string character by character. A countStack (of integers) and a stringStack (of StringBuilders) are used. We also maintain currentString (StringBuilder) for the current level of decoding and k (integer) for the current repetition count. If the character is a digit, we update k. If the character is [, we push the current k onto countStack and the currentString onto stringStack. Then, we reset k and currentString to start a new scope. If the character is ], it signals the end of the current scope. We pop the state from the stacks and combine the strings. If the character is a letter, we simply append it to currentString. After iterating through the entire input string, currentString will hold the final decoded string.
import java.util.Stack; class Solution { public String decodeString(String s) { Stack<Integer> countStack = new Stack<>(); Stack<StringBuilder> stringStack = new Stack<>(); StringBuilder currentString = new StringBuilder(); int k = 0; for (char ch : s.toCharArray()) { if (Character.isDigit(ch)) { k = k * 10 + (ch - '0'); } else if (ch == '[') { // Push the number k and the current string onto the stacks countStack.push(k); stringStack.push(currentString); // Reset for the new substring currentString = new StringBuilder(); k = 0; } else if (ch == ']') { // Pop the state from the stacks StringBuilder decodedString = stringStack.pop(); int repeatCount = countStack.pop(); // Append the repeated current string to the decoded string for (int i = 0; i < repeatCount; i++) { decodedString.append(currentString); } // This becomes the new current string currentString = decodedString; } else { currentString.append(ch); } } return currentString.toString(); }}Complexity
Time
O(M), where M is the length of the decoded output string. Each character is processed once, and string building operations are efficient with `StringBuilder`. The total work is proportional to the final string's length.
Space
O(M), where M is the length of the output string. The stacks can store intermediate strings and counts. The maximum total size of strings stored on the `stringStack` can be proportional to the final output string length M.
Trade-offs
Pros
Efficient O(M) time complexity.
Avoids recursion, thus preventing potential stack overflow errors on extremely deep inputs.
Iterative solutions can have slightly better performance due to no function call overhead.
Cons
Requires managing two stacks, which might be slightly more complex to reason about than the recursive solution for some.
Solutions
Solution
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; }}class Solution: # initial, res being pushed is empty str '' num , res = 0 , '' elif c == ']' : res = str_stk . pop () + res * num_stk . pop () else : res += c return res def decodeString(self, s: str) -> str: num_stk, str_stk = [], [] num, res = 0, '' for c in s: if c . isdigit(): num = num * 10 + int(c) elif c == '[': num_stk . append(num) str_stk . append(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.