Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Decode String

Easy
0/40
Average time to solve is 15m
profile
Contributed by
55 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
All tags
Sort by
Search icon

Interview problems

JAVA SOLUTION || Decode String

import java.util.Stack;
public class Solution 
{
    public static String decodeString(String s) 
    {
       Stack<Integer> numStack=new Stack<>();
       Stack<StringBuilder> strBuild=new Stack<>();
       StringBuilder str=new StringBuilder();


       int num=0;


       for(char c:s.toCharArray()){
           if(c>='0' && c<='9'){
               num=num*10 + c-'0';
           }
           else if(c=='['){
               strBuild.push(str);
               str=new StringBuilder();
               numStack.push(num);
               num=0;
           }
           else if(c==']'){
             StringBuilder temp=str;
               str=strBuild.pop();
               int count = numStack.pop();
               while(count -- > 0){
                   str.append(temp);
               }
           }
           else{
               str.append(c);
           }
       }
       return str.toString();
    }
}
107 views
0 replies
0 upvotes

Interview problems

Easy Solution

#include<bits/stdc++.h>
string decodeString(string s) {
    stack<string> chars;
    stack<int> nums;
    string ans, temp;
    int num=0;
    for(auto x: s) {
        if(isdigit(x)) num=num*10+(x-'0');
        else if(isalpha(x)) ans += x;
        else if(x=='[') {
            nums.push(num); num=0;
            chars.push(ans); ans="";
        }
        else if(x==']') {
            temp=ans;
            for(int i=0;i<nums.top()-1;i++) ans += temp;
            ans=chars.top()+ans;
            chars.pop(); nums.pop();
        }
    }
    return ans;
}
294 views
0 replies
0 upvotes

Interview problems

python solution using stack

def decodeString(s):

    def find(str1,no):

        l = [str1]*int(no)

        return "".join(l)

        

    stack = []

    result = ""

    for i in s:

        if(i!="]"):

            stack.append(i)

        else:

            s1 = ""

            n = stack.pop()

            while n.isdigit() == False and len(stack)>0:

                if(n != "[" and n.isdigit()==False):

                    s1 = n+s1

                n = stack.pop()

            n1 = n

            while n1.isdigit() == True and len(stack)>0:

                n1 = stack.pop()

                if(n1.isdigit()==True):

                    n = n1+n

            if(n1.isdigit() == False):

                stack.append(n1)

            result = find(s1,n)

            stack.append(result)

            #print(result)

            #print(stack)

    return "".join(stack)

105 views
0 replies
0 upvotes

Interview problems

C++ Solution

#include <stack>
#include <string>
#include <cctype>
string decodeString(string s) {
  // write your code here
  stack<int> counts;
  stack<string> resultStack;
  string currentString = "";
  int k = 0;

…  return currentString;
}
167 views
0 replies
0 upvotes

Interview problems

C++ solution : Iterative Traversal on string (With comments)

  • Time Complexity : O(n)
  • Space Complexity : O(n)
  • (Where n is the length of the decoded string)
#include<bits/stdc++.h>
using namespace std;
string decodeString(string s)
{
    int n = s.size();
    string result = "";

    for(int i = 0; i < n; i++){
        /*
        Traverse stirng left to right until a closing bracket is found "]"
        */
        if(s[i] != ']'){
            result.push_back(s[i]);
        }else{
            string temp = "";
            /*
            Until opening bracket is found for 
            the the current close bracket push it into temporart string
            */
            while(!result.empty() && result.back() != '['){
                temp.push_back(result.back());
                result.pop_back();
            }
            /*
            Restore the original order of the string in temp by reversing it
            */
            reverse(temp.begin(), temp.end());
            /*
            Remove the opening bracket from the back of the result string
            */
            result.pop_back();
            /*
            Find number of times the string has to be concatonated by itesef
            */
            string num = "";
            while(!result.empty() && result.back() >= '0' && result.back() <= '9'){
                num.push_back(result.back());
                result.pop_back();
            }
            /*
            Reverse the num string and make it to interger
            */
            reverse(num.begin(), num.end());
            int int_num = stoi(num);
            /*
            Concatonate the temp string num times to the result
            */
            while(int_num){
                result+=temp;
                int_num--;
            }
        }
    }
    return result;
}

beginners

177 views
0 replies
0 upvotes

Interview problems

DecodeString

import java.util.Stack;

public class Solution 
{
    public static String decodeString(String s) 
	{
       Stack<Integer> numStack=new Stack<>();
       Stack<StringBuilder> strBuild=new Stack<>();
       StringBuilder str=new StringBuilder();

       int num=0;

       for(char c:s.toCharArray()){
           if(c>='0' && c<='9'){
               num=num*10 + c-'0';
           }
           else if(c=='['){
               strBuild.push(str);
               str=new StringBuilder();
               numStack.push(num);
               num=0;
           }
           else if(c==']'){
             StringBuilder temp=str;
               str=strBuild.pop();
               int count = numStack.pop();
               while(count -- > 0){
                   str.append(temp);
               }
           }
           else{
               str.append(c);
           }
       }
       return str.toString();
    }
}
189 views
0 replies
0 upvotes

Interview problems

c++ Approch

string decodeString(string s)

{

      stack<string> chars;

        stack<int> nums;

        string res;

        int num = 0;

        for(char c : s) {

            if(isdigit(c)) {

                num = num*10 + (c-'0');                              

            }

            else if(isalpha(c)) {

                res.push_back(c);                

            }

            else if(c == '[') {

                chars.push(res);

                nums.push(num);

                res = "";

                num = 0;

            }

            else if(c == ']') {

                string tmp = res;

                for(int i = 0; i < nums.top()-1; ++i) {

                    res += tmp;

                }

                res = chars.top() + res;

                chars.pop(); nums.pop();

            }

        }

        return res;

}

334 views
0 replies
1 upvote

Interview problems

c++ sol

#include<bits/stdc++.h>

string decodeString(string s)

{

    // write your code here

    stack<char>l;

    for(int i=0;i<s.size();i++){

        if(s[i]!=']')

        l.push(s[i]);

        else{

         string sub="";

            while(l.size()!=0 && l.top()!='['){

            sub=l.top()+sub;

            l.pop();

            }

            l.pop();

        string k="";

        while(l.size()!=0 && l.top()>='0' && l.top()<='9'){

            k=l.top()+k;

            l.pop();

        }

        string a="";

       

        int y=stoi(k);

        while(y!=0){

            a=a+sub;

            y--;

        }

        for (int i = 0; i < a.size(); i++) {

          l.push(a[i]);

        }

        }

    }

    string ans="";

    while(l.size()!=0){

        ans=ans+l.top();

        l.pop();

    }

    reverse(ans.begin(),ans.end());

    return ans;

}

162 views
0 replies
0 upvotes

Interview problems

C++ Approach

#include<bits/stdc++.h>
string decodeString(string s)
{
    // write your code here
    int n=s.length();
    string res="";
    for(int i=0;i<n;i++){
        if(s[i]!=']'){
            res.push_back(s[i]);
        }
        else{
            string str="";
            while(!res.empty() && res.back()!=']'){
                str.push_back(res.back());
                res.pop_back();
            }
            reverse(str.begin(),str.end());
            res.pop_back();
            string nums="";
            while(!res.empty() && res.back()>='0' && res.back()<='9'){
                nums.push_back(res.back());
                res.pop_back();
            }
            reverse(nums.begin(),nums.end());

            int num=stoi(nums);
            while(num){
                res+=str;
                num--;

            }

        }
    }
    return res;
}
224 views
1 reply
0 upvotes

Interview problems

//java solution using Stack :)

import java.util.*; public class Solution  {    public static String decodeString(String s)  {        // Write your code here. Stack<String>st=new Stack<>(); int curnum=0; String curstring="";

for(char c:s.toCharArray()) {    if(c=='[')    {        st.push(curstring);        st.push(Integer.toString(curnum));        curnum=0;        curstring="";    }    else if(c==']')    {       int prevno=Integer.parseInt(st.pop());       String prevstring=st.pop();       StringBuilder sb=new StringBuilder();       for(int i=0;i<prevno;i++)       {           sb.append(curstring);       }       curstring=prevstring+sb.toString();

   }    else if(Character.isDigit(c)) {    curnum=curnum*10+Character.getNumericValue(c); } else {    curstring+=c; } } return curstring;    } }

172 views
0 replies
0 upvotes
Full screen
Console