Decode String - Leetcode 394 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: leetcode.com/problems/decode-...
0:00 - Read the problem
3:45 - Drawing Explanation
12:07 - Coding Explanation
leetcode 394
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#decode #string #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@TheElementFive]

Very comprehensive problem to practice stacks! Together with asteroid collision and daily temps, one can argue understanding those 3 problems alone are a solid prep for stack problems on interviews.

[@Iamnoone56]

this was asked in my amazon sde 1 interview somehow i managed t solved it. holy cow!

[@xinli7477]

Wow, they ask such difficult questions for sde 1? Congrats on solving it!

[@PP-pe3fs]

You have my respect

[@ShivangiSingh-wc3gk]

Did this myself and came to see the solution. I am so happy to see my progress. Thank you soooo much!!!

[@harishsn4866]

I know you probably hear this a lot but your explanations are so clear and easy to grasp. Thanks a ton for this.

[@CostaKazistov]

It's no wonder Google hired him in a heartbeat. NeetCode has a great talent for reducing complex problems into simplest and digestible way.

[@deathbombs]

Great explanation and diagrams!! This is what I got: The things to decode have this pattern: Coefficient(content) 2 things needed:coefficient, and content My approach using stack was adding just the {}, and tracking the indexes for substring , but I like your approach is cleaner by adding everything to stack. General approach: for all chars in string if stack is Empty: if isDigit: calculate the numerical part/coefficient, if (, add to stack, save startindex if is character, add to string builder if stack is not empty: add everything if is ), remove from stack if stack is empty, recursively call helper(s.substring(startIndex+1, endIndex)

[@shubhamshrivastava8649]

Amazingly explained, was able to implement without even looking at code. Thank you!

[@susmi51910]

You explain these problems so well! can you please do a video on the problem " Guess the word" ?

[@jinny5025]

Best explanation as always!

[@amogchandrashekar8159]

You make things feel so easy! Thank you so much 😀

[@varunshrivastava2706]

Then maybe its just me who still didn't understood it.

[@victoronofiok520]

@@varunshrivastava2706 I would ask that you watch it again if so and jott what you can as you follow along Bless🙏

[@arghya_0802]

One of the best solution availabe on YT. Great work sir. Huge fan of the way you break tough and/or complex problems into simpler versions!!😍😍

[@begenchorazgeldiyev5298]

I don't know why I am still using java. I came up with the same solution with a stack but it is at least twice longer thanks to java. This is so easy to read and comprehend.

[@utsavshrestha7162]

Lol same bro. Python is the best language for interviews in my opinion.

[@AnupBhatt]

First coding channel on KZbin that I put the bell icon to receive all updates for !!

[@CostaKazistov]

Same

[@chenhaibin2010]

Great clear explanation as always. thanks

[@Gnaneshh]

Terrific explanation!!

[@kashishshukla23]

Best explanation man! TYSM for your efforts.

[@cherylto5898]

Love your videos, the clearest explainations I've come across among all the other ones ... Keep it up!

[@LeetCodeSimplified]

According to LeetCode premium, the time complexity of this solution is actually O(maxK^countK * n), where maxK is the maximum value of k, countK is the count of nested k values and n is the maximum length of the encoded string. Example, for s = 20[a10[bc]], maxK is 20, countK is 2 as there are 2 nested k values (20 and 10). Also, there are 2 encoded strings a and bc with the maximum length of the encoded string n as 2.

[@wangyex]

This is actually the best tutorial I found on the internet

[@brandenimmerzeel8182]

Thanks, i ended up solving this with recursion on my first attempt. I used this video to learn how to apply stacks to the problem. Thank you.

[@october3518]

wow usually I feel a bit anxious when not able to come up with a soln, I have been watching ur few vids! explanations r crisp and easy to understand, I even like it's in python while I code in cpp lol

[@ren-hauchuang2005]

This is the way better solution than official ones

[@arun-ph9cn]

WOW. the solution and explanation is simply superb!!

[@atulkumar-bb7vi]

Explanation put very simple way, thanks for this!

[@kylefan8478]

this is a very good explanation, very concise and clear code. I implemented this in C++ and got 100% time and 96% memory.

[@watchlistsclips3196]

please send me cpp code i am getting wrong answer in one test case

[@watchlistsclips3196]

This is my code: class Solution { public: string stuff(int n,string s) { string t; while(n--) t+=s; return t; } int stringToNum(string s) { int num=0; for(int i=0;i

[@samridhshubham8109]

A very excellent problem and explanation!

[@pif5023]

Great video! Thanks! This problem showed me stacks are amazing for accruing and backtracking in an organic way!

[@rajdeepchakraborty7961]

Well explained.

[@saifmohamed1776]

i think if we consider the length of the output string is K then the time complx will be linear in this length K -> O(k) ;

[@carloscarrillo201]

You are coding god, man. You're in my idol list, right next Van Halen!

[@dipeshprajapat1203]

Your way of explanation awsome

[@ashutosh1541]

Man this is so easy in python .. i was doing it in C++ . i had the same logic but implementation was so tough for it

[@satya00155]

much easier to understand than upvoted solutions which I could never do interview.

[@matthewb2133]

great video, thanks

[@abhitripathi]

You are amazing, Thanks a lot Lots of love

[@ekanshsharma1309]

thank you so much sir for this amazing explaination🙇‍♂❤

[@ryanc1663]

Thanks bro u the man

[@boybi612]

very neat code

[@nagendrabommireddi8437]

thank you sir

[@kakdi77]

Thanks for the video. Can you also do the Encode verion of this the (Leetcode 471) ?

[@yondensawyers2778]

I solved this a different way in linear time by using two stacks; one of factors where the top of the stack is the last number for the characters and another stack containing the substrings. whenever a ] character is detected it pops the two from their respective stacks, multiplies them, then appends it to the next top of the characters stack.

[@sudoaptinstallrana9572]

can you share your solution i am thinking in the same way

[@prafulparashar9849]

Great explanation !! I was wondering whether we can do it solely by recursion calls?

[@Cloud-577]

yes you can

[@Cloud-577]

recursive is same as maintaining our own stack

[@edwardteach2]

U a God

[@bumpin7789]

How long do you actually take to solve these questions for the first time? It seems to take more than 1.5hrs for me.

[@denni4070]

Just got this for a new grad position and I failed it miserably, should have watched more vids :(

[@k999ford]

Is there a reason you always do range(len(s)) instead of for x in s or enumerate(s)? I've been watching a lot of of these (great) videos and I noticed that, so I'm wondering...

[@everydaylifeisgood]

I was giving this problem for google's phone interview today. I didn't do as well :(

[@ethanwong2272]

It's much easier to write it in Python than in Java.

[@CostaKazistov]

And even easier in Kotlin 😉

[@hhcdghjjgsdrt235]

stack makes this problem pretty much easier

[@ksanjay665]

This was asked in Zoho software developer role

[@amitupadhyay6511]

I did everything same except : substr+=stack.pop() and finally, substr=substr[::-1] and similar for k how m i am failing a test case. Could you please explain the difference ? Failed test case:"3[z]2[2[y]pq4[2[jk]e1[f]]]ef"

[@chenhaibin2010]

I guess you essentially have substr = substr + pop instead of pop + substr, so the order of letters are not the same.

[@watchlistsclips3196]

I even getting the wrong answer in cpp with the same test you failed.Please tell where i did wrong. class Solution { public: string stuff(int n,string s) { string t; while(n--) t+=s; return t; } int stringToNum(string s) { int num=0; for(int i=0;i

[@thanirmalai]

Amazing explanation but i cant think of why i cant solve it by myself

[@Gaurav-ln8ze]

Thank you so much sir for your great and clear explanation. Here the code in c++ :- class Solution { public: string decodeString(string s) { string ans="", substr="", k; int n=s.size(); stack st; for(int i=0; i

[@harshitrathore1744]

Very Nice Explanation. Thanks, Buddy...

[@MeetManga]

should line 16: k = stack.pop() * 10 +k ?

[@CostaKazistov]

Then the digits of K number would be in the wrong order. Popping from the stack retrieves the digits in reverse order. Stepping it through in a debugger makes it easy to see.

[@naodtewodrosasregdew2782]

GOAT

[@crazier192]

The example showed with 54[ab] which has a 2 digits number. But the solution doesn't account for it. Hope you have time to update the video.

[@CostaKazistov]

Actually it does. Line 15 while loop builds a string which then gets converted to Int on Line 17.

[@crazier192]

@@CostaKazistov Thank you! It's my bad, sorry.

[@hoyinli7462]

support

[@willcoomans9674]

what is the space complexity?

[@andrewpaul6251]

It seems leetcode added a testcase and this code no longer works

[@kazirafidraiyan2553]

**This Works** class Solution: def decodeString(self, s: str) -> str: out_str = [] digit = 0 for i in range(len(s)): if s[i] != "]": out_str.append(s[i]) if s[i].isdigit(): digit += 1 else: sub_str = "" while out_str[-1] != "[": sub_str = out_str.pop() + sub_str out_str.pop() n = "" while out_str and out_str[-1].isdigit(): n = out_str.pop() + n n = int(n) out_str.append(int(n)*sub_str) if digit == len(s): return "" else: return "".join(out_str)

[@sellygobeze7173]

🐐

[@greatsunday4780]

It is so difficult to put Sting and Character in the same stack.

[@greatsunday4780]

in java

[@vaidehidharkar3348]

Can someone compare iterative solution vs recursive solution, in terms of time complexity and suggest which one is better approach?

[@dadisuperman3472]

Same thing. No difference

[@tynshjt]

is there another way to solve this without using Stack?

[@himanshuchauhan940]

can anyone help me in solving it in recursively

[@user-xf3li1lk7l]

can any one explain the time complexity of it

[@nanyangbuyuweng]

I don't think the code can cover the corner case as "3"

[@kalyanking1080]

Need recursive solution

[@CostaKazistov]

Recursive solution would be easier to code up, yes. But the above solution would be preferred in an interview setting.

[@rahulpothula1902]

my c++ solution(same logic as explained in the video): class Solution { public: string decodeString(string s) { stack stk; string str = ""; for(auto it: s) { if(it >= 'a' and it = '0' and it = "0" and stk.top() 0) counts = stoi(count); for(int i = 0; i < counts - 1; i++) str += str1; stk.push(str); } } string ans = ""; while(!stk.empty()) { ans = stk.top() + ans.substr(0, ans.length()); stk.pop(); } return ans; } };

[@ChinmayAnaokar-xm4ci]

C# code for above logic : public static class AppHelper { public static String DecodeString(String s) { Stack st = new Stack(); for (int i = 0; i < s.Length; i++) { if (s[i] != ']') { st.Push(s[i]); } else { string curr_str = ""; while (st.Peek() != '[') { curr_str = st.Peek() + curr_str; st.Pop(); } st.Pop(); string number = ""; while (st.Count > 0 && Char.IsDigit(st.Peek())) { number = st.Peek() + number; st.Pop(); } int noKTimes = Convert.ToInt32(number); while (noKTimes > 0) { for (int p = 0; p < curr_str.Length; p++) { st.Push(curr_str[p]); } noKTimes--; } } } s = ""; while (st.Count > 0) { s = st.Peek() + s; st.Pop(); } return s; } }

[@dohunkim2922]

the part where you did “while stack and stack[-1].isdigit():” kinda confuses me. Isn’t the stack always nonempty? There always has to be an integer in front of ‘[‘, otherwise we don’t even need to use brackets. Validating whether the stack is empty or not doesn’t seem to be necessary, but the code doesn’t work if I don’t validate it. I’m so lost here

[@D_T244]

If our input is "23[a]", when we get to line 15 our stack will contain just [2, 3], we have to keep popping numbers but we need to stop once the stack is empty else we'll get an index error when doing stack[-1].isdigit() check. The isdigit() check catches the following case: input = 23[a4[b]] then our stack will be [2, 3, [, a, 4] when we get to that line 15, isdigit() will make sure we don't pop past the number 4 for the current substring we're building.

[@dohunkim2922]

@@D_T244 ohh i didnt consider the case where the integer is a 2digit number. Thansk!!

[@ankitkaushal442]

wow

[@omkarbhale442]

Instead of concatenating to string, I appended them all to a list, and called list.reverse() 😅😅 p.s. Stop scrolling comments, and solve some probolems.

[@user-jr4qw7di9e]

can you do this using recurssion

[@Antinormanisto]

i don't understand why does it work

[@RishirajDesigns]

every time he said "IN PYTHON", I was looking at my Java code, it was like speaking to me: What? don't look at me like that, go and search on google.

[@Tony-un9mg]

GOAT