Remove All Adjacent Duplicates In A String LeetCode
Approach 1: Using Stack :
1. We will create a Stack Of Characters.
2. We will traverse the given string from last.
3. If the stack is empty we will push the i'th indexed character of string into the stack.
Else, we will see whether the peak of the stack is equal to the i'th character of the string.
If it is equal it means adjacent duplicates are found and hance we will pop the stack element.
else we will push that character into the stack.[It means that the character is different from the stack.peek()]
In this way, we will traverse the whole string from last to end.
After traversing we will empty the stack and append all the characters into the StringBuilder object and return to the main function after converting that object to a string.
---------------------------------------------------------------------------------------------------------------------------
public String removeDuplicates(String s) {
Stack<Character> stack=new Stack<Character>();
StringBuilder sb=new StringBuilder();
for(int i=s.length()-1;i>-1;i--){
if(stack.isEmpty()){
stack.push(s.charAt(i));
}
else{
if(stack.peek()==s.charAt(i)){
stack.pop();
}
else{
stack.push(s.charAt(i));
}
}
}
while(!stack.isEmpty()){
sb.append(stack.pop());
}
return sb.toString();
}
----------------------------------------------------------------------------------------------------------------------------
TIME:O(N)[Linear Traversal][LeetCode Time:23ms faster than 53.73% ]
SPACE:O(N)[Stack Usage][LeetCode Space: 40MB less than 51.45%]
Thanks For Reading😇.
"Share Further To Increase Knowledge Treasure😊."
Comments
Post a Comment