View profile

DS Weekly - Reduce the string by removing any pair of adjacent pairs of same letters

Revue
 
 

DS Weekly

December 5 · Issue #4 · View online
Learning data-structures and algorithms need commitment. I'm gonna make it easier by sending you a solved programming challenge weekly from a curated collection of data-structures, algorithms, competitive programming questions, interview questions straight to your mailbox.

Problem Statement
Given a string, reduce the string by removing any pair of adjacent pairs of same letters.
Sample Input 1:
aabccddd
Sample Output:
bd
Sample Input 2:
aaabbcdddd
Sample Output:
ac
Sample Input 3:
cbbc
Sample Output:
Empty String
Solution
This problem is so simple. Logically, we have to find the pair of adjacent letters and delete it. And then we have to traverse the array again and then find the pair of letters again and delete it. We have to repeat the process till no adjacent letters are found. 
The above solution will work. But this is not the optimal solution. 
The optimal solution would be traversing the array once. We can use the stack data-structure to solve this problem optimally. 
Let’s see how
Initially, we start by traversing the array from start. And then if the stack is empty we push the element into the stack.
And for each element, we have to check if the top element of the stack is same as the current element. If it’s same then we pop the top element of the stack or else we push the current element into the stack.
We repeat this process till the end of the string.
That’s it. Simple right. :)
Pseudo Code
Pseudo Code
Pseudo Code
Code Implementation
Java Implementation
Java Implementation
You can find the source code here
Hope you enjoyed it. If you got any feedback reply to this email.
If you think this is helpful don’t mind to share it :) :)
Did you enjoy this issue?
If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Powered by Revue