Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

Leetcode Decode String problem solution

YASH PAL, 31 July 2024

In this Leetcode Decode String problem solution you have 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].

Leetcode Decode String problem solution

Problem solution in Python.

class Solution(object):
    def decode_util(self, s, start):
        i = start
        curr_num = 0
        curr_str = ''
        
        while i < len(s):
            if s[i].isdigit():
                curr_num *= 10
                curr_num += int(s[i])
                i += 1
            elif s[i] in lowercase:
                curr_str += s[i]
                i += 1
            elif s[i] == '[':
                bracket_decode, last_idx = self.decode_util(s, i+1)
                curr_str += (curr_num * bracket_decode)
                i = last_idx + 1
                curr_num = 0
            elif s[i] == ']':
                break
            
        return curr_str, i
                
    
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        return self.decode_util(s, 0)[0]

Problem solution in Java.

class Solution {
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int i = 0; i <s.length();i++) {
            char c = s.charAt(i);
            if (c <= '9' && c >= '0') {
                count = count * 10 + c -'0';
            } else if (c == '[') {
                int j = i+1;
                int open = 1, close = 0;
                i++;
                while (i < s.length() && open != close) {
                    if (s.charAt(i) == '[') open++;
                    else if (s.charAt(i) == ']') close++;
                    i++;
                }
                String sub = decodeString(s.substring(j,--i));
                for (int f = 0; f < count;f++) {
                    sb.append(sub);
                }
                count = 0;
            } else {
                sb.append(c);
            }
        }
        
        return sb.toString();
    }
}

Problem solution in C++.

class Solution {
private:
    string selfConcat(const string& s, int times) {
        string out;
        
        for (int i = 0; i < times; ++i) {
            out.append(s);
        }
        
        return out;
    }
public:
    string decodeString(const string& s) {
        stack<int> multiplierS;
        stack<string> stringS;
        multiplierS.push(1);
        stringS.push("");
        
        int currMultiplier = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (isdigit(s[i])) {
                currMultiplier *= 10;
                currMultiplier += (s[i] - '0');
            } else if (s[i] == '[') {
                stringS.push("");
                multiplierS.push(currMultiplier);
                
                currMultiplier = 0;
            } else if (s[i] == ']') {
                int topMult = multiplierS.top(); multiplierS.pop();
                string topS = stringS.top(); stringS.pop();
                
                string decodedTop = selfConcat(topS, topMult);
                topS = stringS.top(); stringS.pop();
                
                stringS.push(topS + decodedTop);
            } else {
                stringS.top().push_back(s[i]);
            }
        }
        
        return stringS.top();
    }
};

Problem solution in C.

#define MAX_SIZE_STR_OUT 10000

char * helper(char *str_in,int *idx_in);

char * decodeString(char * s){
    if(!s)return NULL;
    char str_out[MAX_SIZE_STR_OUT];
    
    char * str_new;
    int idx_out=0,idx=0;
    
    while(s[idx]!=''){
        while((s[idx]>='a'&&s[idx]<='z')||(s[idx]>='A'&&s[idx]<='Z'))str_out[idx_out++]=s[idx++];
        str_new=helper(s,&idx);
        strcpy(&str_out[idx_out],str_new);
        idx_out+=strlen(str_new);
        free(str_new);  
    }
   
str_out[idx_out++]=0;    
char * str_ret = (char*)malloc(idx_out);
strcpy(str_ret,str_out);
return str_ret;
}


//to do remove the ' from strings

char *helper(char *str_in,int *idx_in){
    if(!str_in)return NULL;
    char * str_out = (char*)malloc(MAX_SIZE_STR_OUT);
    char * str_new;
    int idx_out=0,number =0,new_number=0;
    
    while(str_in[*idx_in]!=''){
        if((str_in[*idx_in]>='a'&&str_in[*idx_in]<='z')||
           (str_in[*idx_in]>='A'&&str_in[*idx_in]<='Z'))str_out[idx_out++]=str_in[*idx_in];
           
       else if(str_in[*idx_in]>='0'&&str_in[*idx_in]<='9'){
            new_number=0;
            if(!number){
                while(str_in[(*idx_in)]>='0'&&str_in[(*idx_in)]<='9'){
                new_number= new_number*10+(str_in[(*idx_in)]-'0');
                (*idx_in)++;
                }
                number =new_number;
            }
            else{
                str_new=helper(str_in,idx_in);
                strcpy(&str_out[idx_out],str_new);
                idx_out+=strlen(str_new);
                (*idx_in)--;
                free(str_new);
            }
        }
        
        else if(str_in[*idx_in]==']'){
            for(int i=0;i<number;i++)memcpy(&str_out[i*idx_out],str_out,idx_out);
            idx_out=number*idx_out+1;
            idx_out--;
            str_out[idx_out]=0;
            (*idx_in)++;
            return str_out;
        }
        (*idx_in)++;  
    }
str_out[idx_out]=0;
return str_out;
}

coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes