algoadvance

Leetcode 394. Decode String

Problem Statement

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; 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 won’t be input like 3a or 2[4].

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"

Clarifying Questions

  1. Q: Can the input string have nested brackets?
    • A: Yes, the input string can have nested brackets, as seen in example 2.
  2. Q: Are there any constraints on the length of the input string?
    • A: The problem statement does not specify, but typically we can assume reasonable sizes for string inputs in coding challenges on LeetCode.
  3. Q: Are all characters inside the brackets guaranteed to be lowercase English letters?
    • A: Yes, the problem guarantees that the encoded strings contain lowercase English letters.

Strategy

To solve this problem, we need to deal with nested structures and repetitions. We can use a stack-based approach to handle this efficiently.

Plan:

  1. Initialize two stacks: one for counts and one for strings.
  2. Iterate through the string character by character:
    • If the character is a digit, calculate the full number (it can be more than one digit).
    • If the character is [, push the current number and the current result string onto their respective stacks, then reset them.
    • If the character is ], pop from both stacks and construct the repeated string, then concatenate it to the previous result string.
    • For other characters (lowercase letters), add them to the current result string.
  3. At the end, the result string will contain the fully decoded string.

Example Trace:

For s = "3[a2[c]]":

Code

#include <iostream>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    string decodeString(string s) {
        stack<int> counts;
        stack<string> strings;
        string result;
        int idx = 0;
        
        while (idx < s.size()) {
            if (isdigit(s[idx])) {
                int count = 0;
                while (isdigit(s[idx])) {
                    count = count * 10 + (s[idx] - '0');
                    idx++;
                }
                counts.push(count);
            } else if (s[idx] == '[') {
                strings.push(result);
                result = "";
                idx++;
            } else if (s[idx] == ']') {
                string temp = result;
                result = strings.top();
                strings.pop();
                int count = counts.top();
                counts.pop();
                while (count > 0) {
                    result += temp;
                    count--;
                }
                idx++;
            } else {
                result += s[idx];
                idx++;
            }
        }
        
        return result;
    }
};

// Example usage:
int main() {
    Solution solution;
    string s = "3[a2[c]]";
    cout << "Decoded String: " << solution.decodeString(s) << endl; // Output: "accaccacc"
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string. We process each character of the input string exactly once, and the operations performed in each step (push, pop, and concatenate) are efficient. The space complexity is also O(n) due to the additional stacks used to store counts and substrings.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI