Sir, even if we form string in reverse and compare also it will accept , because checking equality no matter of from front or end. if we form string by placing character at 0 index takes much time then placing at end.
The question clearly mentioned to solve the problem with O(1) space complexity. You solution takes O(n) space. Though it is getting accepted, it is ideally wrong. Can you pls change it to O(1) space.
that is the follow up question and it got added recently to LeetCode problem statement. I will put up something in the comments or expand the solution on Github. Thanks for bringing it to my notice 👍
Hello @Nikhil, Can you create a video on Two pointer approach please, I know there are many videos out there, but your explanation will help me better understanding, please read this comment and help us all.
If you havent got it already, Its similar to the solution given by Nikhil. Whenever we encounter a '#' just pop the top most character and in the end compare the two strings
.create two new stacks..one for storing alphabest and one for storing hashes....iterate through the string....if u encounter an aplhabet add it to the alphabet stack.....if u encounter a hash add it to the hash stack...now compare the size of two stacks...subtract the sizes...now if the size of hash stack is equal to the length of the alphabet stack...the answer will be an empty string if not...if the alphabet stack is longer than the hash stack....keep popping the elements one by one and as the hash stack would be empty,...the remaining element/elements in the alphabet stack would be returned as a string as the answer...the time complexity would be O(N) approximately if we ignore the O(1) time taken to add and pop the elements...and also we'll only iterate thru the string once....space complexity will be O(N+M) the sizes of newly created stacks
