Recursively remove all adjacent duplicates

In this blog we are discussing a problem asked by paytm, samsung.

Problem:

Given a strings, recursively remove adjacent duplicate characters from the string s. The output string should not have any adjacent duplicates.

Input:

The first line of input contains a string str.

Output:

Print a new line containing the resulting string.

Constraints:

1 <= Length of string <= 50

Example:

Input 1:

programmersdoor

Output 1:

prograersdr

Input 2:

abccabbdadd

Output:

abada

---

Implementation Using C++:

#include <iostream>
#include <string.h>
using namespace std;

// removes all adjacent duplicates from
char* removeAdjacentDuplicate(char* str, int n)
{
	// k maintains the index of next free location in the result
	// and i maintains the current index in the string
	int i, k = 0;
	int len = strlen(str);

	// start from second character
	for (i = 1; i < len; i++)
	{
		// if current char is not same as the
		// previous char, add it to result
		if (str[i - 1] != str[i])
			str[k++] = str[i - 1];
		else
		{
			// remove adjacent duplicates
			while (i < len && str[i - 1] == str[i])
				i++;
		}
	}

	// Add last character to result
	str[k++] = str[i - 1];

	// null terminate the string
	str[k] = '\0';

	if (k != n)
		return removeAdjacentDuplicate(str, k); 
		
	return str;
}

int main()
{
	char str[] = "programmersdoor";
	int n = strlen(str);

	cout <<removeAdjacentDuplicate(str, n);

	return 0;
}

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

---

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #string #manipulation #paytm #samsung