Decode String

Easy
0/40
Average time to solve is 15m
profile
Contributed by
60 upvotes
Asked in companies
DelhiveryPaytm (One97 Communications Limited)Ola

Problem statement

You have been given an encoded string. Your task is to decode it back to the original string.

- An encoded string will be of the form <count>[encoded_string], where the 'encoded_string' inside the square brackets is being repeated exactly 'count' times. Note that 'count' is guaranteed to be a positive integer and can be greater than 9.
- There are no extra white spaces and square brackets are well-formed.
For example -
Input: 2[a]
“a” is encoded 2 times, hence the decoded string will be "aa".

Input: 3[a2[b]]
“b” is encoded 2 times, which decodes as 3[abb]. Now, "abb" is encoded 3 times, hence decoded string will be "abbabbabb". 
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The only line of each test case contains a string 'S' which represents the encoded string. 
Output Format:
For each test case, print a string i.e. the decoded string.

Output for every test case will be printed in a separate line.

Note: You are not required to print the expected output, it has already been taken care of. Just implement the function. 
Constraints:
 1 <= T <= 20
 1 <= |S| <= 500

 where |S| is the length of the Decoded string.

 Time limit: 0.400 sec
Sample Input 1:
2
3[a]2[bc]
a1[b]1[cc]
Sample Output 1:
aaabcbc
abcc
Explanation for sample 1:
For the first test case, "a" is encoded 3 times and "bc" is encoded 2 times. After combining these two strings after decoding, we'll get "aaa" + "bcbc" = "aaabcbc".
Sample Input 2:
1
ab2[c3[b]]
Sample Output 2:
abcbbbcbbb
Hint

Try to keep track of the current string and the number of times it needs to be repeated using stack.

Approaches (1)
Stack Solution

The idea is to maintain two Stacks. One will store the integers i.e. number of times the current string is repeated and the other one will store the strings itself. 

We use a simple idea and always evaluate the innermost brackets first. We traverse through our encoded string

  • If we encounter an integer, we push it onto our ‘integerStack’.
  • If we encounter a character, then we simply append it to the ‘currentString’.
  • Whenever we encounter an open bracket ‘[‘, we push the ‘currentString’ onto the ‘stringStack’ and start a new empty string as the ‘currentString’.
  • Once, we encounter a closing bracket ‘]’, that means we have to repeat the 'currentString'.
    • So, we extract the top element of ‘integerStack’ (say K).
    • We extract the top element of ‘stringStack’ (say 'previousString').
    • We repeatedly concatenate the currentString K times to the ‘previousString’.
    • Then, we update the ‘currentString’ to the new 'previousString'.
  • Return the ‘currentString’ as our decoded string.
Time Complexity

Time Complexity for this question is language-dependent.

O(N^2), where N is the length of the DECODED STRING,  for languages that perform string concatenation in linear time(ex - Python).

O(N) for languages that perform string concatenation in constant time(ex - C++).

Space Complexity

O(N),  where N is the length of the DECODED STRING. 

We require space as much as the length of the final decoded string. Hence, complexity is linear.

Code Solution
(100% EXP penalty)
Decode String
Full screen
Console