Remove adjacent duplicates in a string

This video explains how to remove adjacent duplicates from a string. The lecture explains the intuition with help of code which is dry run in the video itself. This is a frequent coding round as well as interview round programming question. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[@divyagupta6854]

Thanks, this video really helped me to grasp the concept behind the problem. Just a thing want to add, when input is given as an array of integers, this exact code will not work, and we need to check another condition at first line of outer loop, to prevent array index out of bounds exception.

[@subhamsekharpradhan297]

Sir this code is showing index error in the inner while loop, what needs to be changed?

[@DeepakSingh-bd6mk]

for this case: abccbccba
it is giving abbba but it should be null

[@factzzseeker1233]

bcz it is wrong ,apply your brain only

[@Liv_Life]

@@factzzseeker1233 nyc

[@shikujha4141]

Just add on more line of code
If(res==s) return res and break;
Else continue;

[@notondrugs5860]

how can we do it recursively?

[@khakr01]

In leetcode example, for a given input - "abbaca" the output was - "ca" instead of "aaca" .. basically it is again reducing the aaca to "ca". Could you elaborate for one such example

[@techdose4u]

Can you please read the answer given to Ritwik Jain. I have explained there.

[@tilakrajrao2753]

@@techdose4u there is no comment from Ritwik jain is showing here sir. could you please tell once again??

[@sayantaniguha8519]

Question link?

[@imshivendra]

Is this problem is similar to remove adjacent duplicates in a string at geeksfoegeeks.Please tell me.
Input:
S = aabb
Output: ab
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
Similiar explanation for b at
4th position.

[@the.arty.heart_]

@@imshivendra No, it would be same if at end of sir's code you again call the same function

[@025_basharatnawaz4]

according to me.
there is one more condition need to be check.
before putting a character into the result
check if(character != res.back())
then res.push_back(character);
else
simply skip the character.

[@ShivamKumar-oh9bw]

not just skip , we have to do res.pop_back() also

[@imshivendra]

Is this problem is similar to remove adjacent duplicates in a string at geeksfoegeeks.Please tell me.
Input:
S = aabb
Output: ab
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
Similiar explanation for b at
4th position.

[@AlmogYosef520]

Do you use a dynamic array here In order to save the new string ? if so, can you explain without the help of dynamic array to store a string ? I want to know how can i update the current string without the help of another string. Thanks !

[@techdose4u]

I am not using any type of array. The only thing being used is the string res (you may think res to be a char type array). I will store the result of one operation of the string in res and then i will again repeat the entire algo. Keep repeating untill you traverse the entire string without having to delete any character (this is the breaking condition). Please read the pinned comment to understand the method of solving. If you still face any problem then do let me know.

[@imshivendra]

Is this problem is similar to remove adjacent duplicates in a string at geeksfoegeeks.Please tell me.
Input:
S = aabb
Output: ab
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
Similiar explanation for b at
4th position.

[@imshivendra]

Is this problem is similar to remove adjacent duplicates in a string at geeksfoegeeks.Please tell me.
Input:
S = aabb
Output: ab
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
Similiar explanation for b at
4th position.

[@crazyboy-gw7rk]

Can you give recursive approach
I/p -> "axeexc" o/p->"ac"

[@Kushagra_21]

#code
T=int(input())
for _ in range(T):
s=input()
res=""
if (len(s) == 0 or len(s) == 1):
print(s)
else:
for i in range(len(s)):
while(s[i]):
if(s[i]!=s[i+1]):
res+=(s[i])
i+=1
if(s[i+1] and s[i]==s[i+1]):
while(s[i+1] and s[i]==s[i+1]):
i+=1
i+=1
print(res)
this is the code i wrote but its giving string index out of range .....can you plzz help out in this

[@vijayatest5373]

Very good explanation. Thank you !!

[@techdose4u]

Thanks :)

[@imshivendra]

Is this problem is similar to remove adjacent duplicates in a string at geeksfoegeeks.Please tell me.
Input:
S = aabb
Output: ab
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
Similiar explanation for b at
4th position.

[@tejeshwarshivanandan4966]

Assume i is the last char will it not raise an error while comparing i!=i+1 as i+1 is out of range?

[@techdose4u]

You will not run in that case. Need to handle the boundary case.

[@tejeshwarshivanandan4966]

Can you send me the link of your code please?

[@kunnudev7250]

Sir greetings great job please continue awesome videos salute to you brother awesome videos plz make more videos like these thanks a lot

[@ut100mishra]

Please tell the recursive approach too

[@ash_engineering]

Using a stack gives a more elegant solution . In O(n) time and O(n) space complexity and guarantees to work for all input cases .

[@techdose4u]

Yea correct.

[@ericcartman4799]

@Arun: Can you share the code using stack. I have implemented using stack but it fails for the case "MISSISSIPIE "

[@imshivendra]

Is this problem is similar to remove adjacent duplicates in a string at geeksfoegeeks.Please tell me.
Input:
S = aabb
Output: ab
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
Similiar explanation for b at
4th position.

[@pranas2493]

What about set

[@utkarshgupta2909]

for each elem compare just left and right .. anyone of them shouldnot be equal to current one. if not print it. For i==0 compare with a[1] and for last compare a[n-1] with just a[n-2] (corner case). Also tell if I my approach is wrong

[@spetsnaz_2]

impressive explanation.!

[@techdose4u]

Thanks :)

[@michaelscott4830]

Very helpful 🙏

[@HomemadeTechARC08]

Is there any approach less than o(n)

[@techdose4u]

I don't think there can be an approach of lower time than O(N) because you atleast need to read all the characters in order to either eliminate or store in result.

[@rakshith3547]

This is not the exact sol for 1047. Remove All Adjacent Duplicates In String problem. It is not handling a case when input is "abbaca"

[@learn_fun_miss]

Recursively call this method gives correct result.

[@praveenreddychalamalla]

But it goes to O(n^2) if you call the method recursively. Worst Case input leading to O(n^2) could be an even length palindrome!!

[@HimanshuSharma-tm2ms]

a simple solution is (O(n))
#not including the edge cases like index 0 or n-1
if( a[i] != a[i+1] && a[i]!=a[i-1]) #if arr[i] not equal to element ahead of it and behind it then add it to result
res+=a[i];
Now I am assuming that we don't have to go over the res also to make it non repeating type

[@abhishekvadnagara236]

Can I do like this
res[j]=s[i]
i++;
j++;
Instead of res+=s[i]
Pls reply

[@nettemsusrinivas2046]

Good explanation

[@techdose4u]

Thanks :)

[@fb_a]

it takes *O(n^2)* time for palindrome type strings like *abcdeedcba* , this algorithm has to be repeated for each result until we don't find any adjacent duplicates in particualr result.
as we have to consider worst case for time complexity so we have to do it (n+n-2+n-4+n-6.....) times, it takes O(n^2)

[@techdose4u]

You can take a stack and easily do it in O(N) time. Just keep pushing and whenever you find like elements, just pop the top and don't push the present. Move to next element. This is the optimized soln in O(N). I hope you got it.

[@fb_a]

Stack solution fails for
*baaab* and
*IssIssI* kind of cases

[@techdose4u]

For these type of cases you need to remember the last character which got removed so as to handle the odd number of characters. This is a boundary case and easy to handle. Its simple to implement. Isn't it.

[@dashrathyadav1476]

@@techdose4u "Mississippi"...what about this..

[@praveenreddychalamalla]

@@techdose4u Even if we remember the last character which got removed, it fails. Eg: abccbccba . The answer will be "" empty string but we end up getting answer as "aba" which is wrong one

[@justineandru]

Why there is string index out of bound exception

[@techdose4u]

Where??

[@divyatejaswinivengada6368]

Good one man! (y)

[@techdose4u]

Thanks :)

[@SiddharthRay1]

best explanation of an algorithm ❤️

[@techdose4u]

:)

[@saarthjhaveri8716]

abccbccba what is the ans for this?

[@SatyaPrakash-il2ed]

Dude why you stopped uploading? You ok ?

[@avinashg.k8166]

in python the code will be like bellow one
a = input()
array = []
i = 0
try:
while True:
if a[i] != a[i+1] or len(a)-1 == i:
array.append(a[i])
i += 1
if a[i] == a[i+1]:
while a[i] == a[i+1]:
i += 1
i += 1
except:
pass
if a[-1] != a[-2]:
array.append(a[-1])
for i in array:
print(i, end="")

[@shivanshrawat2688]

Can i prepare from amazon interview from your site in two months?

[@techdose4u]

Definitely yes

[@pixelsbyme]

no

[@rithikraj1813]

Eg alg diya h aur accept alg chiz ke basis mei krra h gfg idk why abccbccba iska null nii anaa chaiye eg se aba aana chahiye but null lera h 😓😓

[@shreyaboinpally5255]

it doesnt work for acaaabbbcdddd

[@nehasharma6171]

thank you

[@aravindhkumar3640]

Try to make continues video

[@techdose4u]

Whenever I get time from office I do make videos :)

[@AnkitYadav-tz3ph]

Above program may not work for 'caaabbbaacdddd'

[@1988respect]

this will:
const removeAdjecentDuplicate = function(input) {
const result = [];
let isInserted = false;
for(let i = 0; i < input.length; i++) {
if(input[i] && input[i] !== input[i+1]) {
result.push(input[i]);
} else {
while(input[i] && input[i] === input[i+1]) {
isInserted = true;
i++;
}
}
}
console.log(result.join(''), 'isInserted', isInserted);
if(!isInserted) {
return result.join('');
} else {
return removeAdjecentDuplicate(result.join(''));
}
}

[@iit_da_munda]

Shouldn't the answer be a?

[@poonamagrawal8596]

mississipie
output coming as miiipie
output should be mpie

[@nimishgupta5289]

On what you write?

[@techdose4u]

Did not get your question! Please elaborate.

[@nimishgupta5289]

@@techdose4u on what do you write.... means it is not pen paper not a black board, then what is it...

[@mayurkapadnis4265]

Recursive way is more efficient

[@techdose4u]

👍🏼

[@mrudul5018]

I think this solution is wrong for gfg test cases

[@QVL75]

No way you can solve this with O(n) time and no extra space.

[@techdose4u]

With extra space O(N) and Time O(N)---> Use stack.

[@saigopalraopeechara6912]

@@techdose4u cant we use erase function and delete adjacent duplicates in the string itself so that no extra space will be taken?
int main(){
string s;
cin>>s;
int i=0, j=0;
while(s[i]){
if(s[i]!=s[i+1])
i++;
else{
j=i;
while(s[i+1]&&s[i]==s[i+1])
i++;
s.erase(j,i-j+1);
i=j;
}
}
cout

[@ericksibrian6981]

He could have used a whole keyboard but decided to draw chicken scratch instead. awesome!!!

[@techdose4u]

😅

[@pushpendrahpx]

its incomplete bro

[@ayushgarg5929]

Question's name should rather be Recursively remove adjacent duplicates in a string

[@techdose4u]

I missed the most optimized approach using stack.

[@ayushgarg5929]

@@techdose4u sir i have also seen that stack approach ...that's also does not work in all cases.

[@ranselynigrel8714]

For below code I am facing issue
class Solution
{
public String removeDuplicates(String s)
{
String result ="";
int i;
//int len = s.length();
//char s[]= p.toCharArray();
for(i=0;i

[@mohitmotwani9256]

CODE FOR THE ABOVE EXPLANATION
string removeUtul(string& s)
{
int n = s.size();
int i = 0;
string res;
while( i < n)
{
if(i < n-1 && s[i] == s[i+1])
{
while(i < n-1 && s[i] == s[i+1])
{
i++;
}
}
else
res.push_back(s[i]);
i++;
}
return res;
}
string remove(string s){
string res = s;
string temp;
while(temp.size() != res.size())
{
temp = res;
res = removeUtul(res);
}
return res;
}

[@nikhilrauniyar9084]

Simplest thing to do in c++;
if that letters in s string match the ans string you remove the letters from ans string otherwise you push in the letters that do not match into the ans string. Might be the easiest explanation available
class Solution {
public:
string removeDuplicates(string s) {
string ans;
for(int i = 0; i

[@lucratividadedocanal981]

for (int i = 0; i < input.Length; i++)
{
if (i == 0){
result += input[i];
}
else if (input[i] != result[result.Length - 1])
{
result += input[i];
}
}

[@lucratividadedocanal981]

another way
var regex = new Regex("(.)\\1+");
result = input;
return regex.Replace(result, "$1");

[@goutamhalder9871]

int i=0;
while(i

[@rahulbajetha4057]

Those who wants recursively remove adjacent duplicates :
For Ex. I/P : accabbax O/P : x
string remove(string s){
int f=0,i=0;
string res;
while(i

[@imshivendra]

Is this problem is similar to remove adjacent duplicates in a string at geeksfoegeeks.Please tell me.
Input:
S = aabb
Output: ab
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
Similiar explanation for b at
4th position.

[@vedanshsharma1156]

nicce