Decode String - Leetcode 394 - Python

[@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.

[@ShivangiSingh-wc3gk]

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

[@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

[@gazijarin8866]

The fact that you appended the string AFTER the pop made the problem so easy. I was shaking my head in horror trying to reverse the string once after appending it.

[@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)

[@SriHarishPopuri]

The sub string calculation in this solution (which is done twice btw) is a costly operation to do, both in time and space. Strings are immutable and this above way of calculating substrings can lead to quadratic time complexity when calculating the multiplier or inner string between square brackets, when there are large inputs. Instead, the characters can be appended to a list and joined using "".join(list) method, which will have linear time complexity. Thats a lot better in terms of the time and space complexities.

[@susmi51910]

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

[@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🙏

[@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.

[@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

[@shubhamshrivastava8649]

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

[@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.

[@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.

[@chrischika7026]

yup, hope you made the siwtch.

[@pif5023]

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

[@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!!😍😍

[@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) ;

[@thndesmondsaid]

aw man, tried this on my own and thought to use a stack but couldn't figure out the algo. Thank you!

[@AnupBhatt]

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

[@CostaKazistov]

Same

[@ren-hauchuang2005]

This is the way better solution than official ones

[@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

[@iamcarlostovias]

This was my original intuition as well.

[@cherylto5898]

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

[@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.

[@wangyex]

This is actually the best tutorial I found on the internet

[@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

[@adityavikrant3847]

Great solution! Could you explain why we need to check whether the stack exists before popping digits?

[@arun-ph9cn]

WOW. the solution and explanation is simply superb!!

[@samridhshubham8109]

A very excellent problem and explanation!

[@atulkumar-bb7vi]

Explanation put very simple way, thanks for this!

[@pushpitkaushik7609]

How are you accounting for this edge case ? “vvvlo” Your algo would return “vlovv” or “” Where a string is possible “vlvov”

[@kashishshukla23]

Best explanation man! TYSM for your efforts.

[@jinny5025]

Best explanation as always!

[@prafulparashar9849]

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

[@Cloud-577]

yes you can

[@carloscarrillo201]

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

[@Gnaneshh]

Terrific explanation!!

[@chenhaibin2010]

Great clear explanation as always. thanks

[@dipeshprajapat1203]

Your way of explanation awsome

[@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.

[@ekanshsharma1309]

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

[@kakdi77]

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

[@joydeep_]

Phenomenal explanation!!

[@everydaylifeisgood]

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

[@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...

[@ethanwong2272]

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

[@CostaKazistov]

And even easier in Kotlin 😉

[@Cloud-577]

recursive is same as maintaining our own stack

[@abhitripathi]

You are amazing, Thanks a lot Lots of love

[@ksanjay665]

This was asked in Zoho software developer role

[@hhcdghjjgsdrt235]

stack makes this problem pretty much easier

[@denni4070]

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

[@nemesis_rc]

Well explained.

[@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

[@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

[@boybi612]

very neat code

[@thanirmalai]

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

[@tynshjt]

is there another way to solve this without using Stack?

[@willcoomans9674]

what is the space complexity?

[@matthewb2133]

great video, thanks

[@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)

[@nagendrabommireddi8437]

thank you sir

[@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.

[@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; } };

[@harshitrathore1744]

Very Nice Explanation. Thanks, Buddy...

[@nanyangbuyuweng]

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

[@greatsunday4780]

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

[@greatsunday4780]

in java

[@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; } }

[@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.

[@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!!

[@naodtewodrosasregdew2782]

GOAT

[@ryanc1663]

Thanks bro u the man

[@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

[@prajwals8203]

Will the interviewer accept regex?

[@edwardteach2]

U a God

[@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.

[@shivamvishawakarma-z6o]

can any one explain the time complexity of it

[@himanshuchauhan940]

can anyone help me in solving it in recursively

[@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.

[@hoyinli7462]

support

[@YohannesAsfaw-b8b]

can you do this using recurssion

[@Antinormanisto]

i don't understand why does it work

[@sellygobeze7173]

🐐

[@ankitkaushal442]

wow

[@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