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.
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.
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)
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
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.
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.
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.
Amazing solution as always. Instead of checking for "[" and popping twice, I used not(stack[-1].isdigit()). Then, in the first while loop, break if the popped value is "["
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
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.
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...
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"
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
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
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
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.
**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)
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.
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.
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.
Did this myself and came to see the solution. I am so happy to see my progress. Thank you soooo much!!!
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.
this was asked in my amazon sde 1 interview somehow i managed t solved it. holy cow!
Wow, they ask such difficult questions for sde 1? Congrats on solving it!
You have my respect
I know you probably hear this a lot but your explanations are so clear and easy to grasp. Thanks a ton for this.
It's no wonder Google hired him in a heartbeat.
NeetCode has a great talent for reducing complex problems into simplest and digestible way.
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)
You make things feel so easy!
Thank you so much 😀
Then maybe its just me who still didn't understood it.
@@varunshrivastava2706 I would ask that you watch it again if so and jott what you can as you follow along
Bless🙏
this is a very good explanation, very concise and clear code. I implemented this in C++ and got 100% time and 96% memory.
please send me cpp code i am getting wrong answer in one test case
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
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.
First coding channel on UA-cam that I put the bell icon to receive all updates for !!
Same
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.
Amazingly explained, was able to implement without even looking at code. Thank you!
You explain these problems so well! can you please do a video on the problem " Guess the word" ?
You are coding god, man. You're in my idol list, right next Van Halen!
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.
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.
Lol same bro. Python is the best language for interviews in my opinion.
yup, hope you made the siwtch.
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!!😍😍
Amazing solution as always. Instead of checking for "[" and popping twice, I used not(stack[-1].isdigit()). Then, in the first while loop, break if the popped value is "["
Love your videos, the clearest explainations I've come across among all the other ones ... Keep it up!
This is the way better solution than official ones
aw man, tried this on my own and thought to use a stack but couldn't figure out the algo. Thank you!
This is actually the best tutorial I found on the internet
Great video! Thanks! This problem showed me stacks are amazing for accruing and backtracking in an organic way!
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) ;
Best explanation man! TYSM for your efforts.
Best explanation as always!
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
much easier to understand than upvoted solutions which I could never do interview.
Terrific explanation!!
A very excellent problem and explanation!
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.
can you share your solution i am thinking in the same way
This was my original intuition as well.
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
Great explanation !!
I was wondering whether we can do it solely by recursion calls?
yes you can
Explanation put very simple way, thanks for this!
Great solution! Could you explain why we need to check whether the stack exists before popping digits?
WOW. the solution and explanation is simply superb!!
Phenomenal explanation!!
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...
Your way of explanation awsome
How long do you actually take to solve these questions for the first time? It seems to take more than 1.5hrs for me.
Great clear explanation as always. thanks
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"
I guess you essentially have substr = substr + pop instead of pop + substr, so the order of letters are not the same.
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
what a code! beauty!
How are you accounting for this edge case ? “vvvlo”
Your algo would return “vlovv” or “”
Where a string is possible “vlvov”
Thanks for the video. Can you also do the Encode verion of this the (Leetcode 471) ?
You are amazing, Thanks a lot
Lots of love
Well explained.
It's much easier to write it in Python than in Java.
And even easier in Kotlin 😉
very neat code
thank you so much sir for this amazing explaination🙇♂❤
great video, thanks
recursive is same as maintaining our own stack
stack makes this problem pretty much easier
This was asked in Zoho software developer role
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
I was giving this problem for google's phone interview today. I didn't do as well :(
Just got this for a new grad position and I failed it miserably, should have watched more vids :(
what is the space complexity?
Thanks bro u the man
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
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.
@@D_T244 ohh i didnt consider the case where the integer is a 2digit number. Thansk!!
It seems leetcode added a testcase and this code no longer works
**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)
Amazing explanation but i cant think of why i cant solve it by myself
should line 16: k = stack.pop() * 10 +k ?
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.
thank you sir
is there another way to solve this without using Stack?
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.
Actually it does.
Line 15 while loop builds a string which then gets converted to Int on Line 17.
@@CostaKazistov Thank you! It's my bad, sorry.
GOAT
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;
}
}
I don't think the code can cover the corner case as "3"
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;
}
};
Can someone compare iterative solution vs recursive solution, in terms of time complexity and suggest which one is better approach?
Same thing.
No difference
U a God
It is so difficult to put Sting and Character in the same stack.
in java
Very Nice Explanation. Thanks, Buddy...
can any one explain the time complexity of it
Will the interviewer accept regex?
support
can anyone help me in solving it in recursively
Need recursive solution
Recursive solution would be easier to code up, yes.
But the above solution would be preferred in an interview setting.
🐐
can you do this using recurssion
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.
i don't understand why does it work
wow
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.
GOAT