Decode String

Hi geeks, in this article, we going to solve one interesting problem in leetcode, that is Decode string. It tests our analytical and problem solving skills.

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"

Example 4:

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

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

Solution

To solve this problem, we going to play with Stack Data Structure. Its quite interesting.

  1. Let’s have two stacks, one to track the integer numbers in a string and the other to track the previously updated string. It’s a very simple problem.
  2. When we get an alphabetic character we just append it in our result string.
  3. When we get an integer digit, make sure to track the complete number, so it avoids many traps in the problem.
  4. Close square bracket and the open square bracket is the key point, where our logics mainly stays there.

Let’s look the below program for deep understanding.

Java Program

public class Solution {
    public String decodeString(String s) {
        String res = "";
        Stack countStack = new Stack<>();
        Stack resStack = new Stack<>();
        int idx = 0;
        while (idx < s.length()) {
            if (Character.isDigit(s.charAt(idx))) {
                int count = 0;
                while (Character.isDigit(s.charAt(idx))) {
                    count = 10 * count + (s.charAt(idx) - '0');
                    idx++;
                }
                countStack.push(count);
            }
            else if (s.charAt(idx) == '[') {
                resStack.push(res);
                res = "";
                idx++;
            }
            else if (s.charAt(idx) == ']') {
                StringBuilder temp = new StringBuilder (resStack.pop());
                int repeatTimes = countStack.pop();
                for (int i = 0; i < repeatTimes; i++) {
                    temp.append(res);
                }
                res = temp.toString();
                idx++;
            }
            else {
                res += s.charAt(idx++);
            }
        }
        return res;
    }
}


Time Complexity: O(n) * (number of integer size and count)

Space Complexity: O(n)

Leave a Comment

Your email address will not be published. Required fields are marked *