Remove all adjacent duplicates from a string
Given a string, remove all adjacent duplicates from it. The algorithm should continue removing adjacent duplicates from the string till no duplicate is present in the result.
For example,
The input string is 'DBAABDAB'
The string left after the removal of all adjacent duplicates is 'AB'
'DBAABDAB' —> 'D B
The input string is 'ABADB'
The string left after the removal of all adjacent duplicates is 'ABADB'
'ABADB' —> 'ABADB'
The input string is 'ABDAADBDAABB'
The string left after the removal of all adjacent duplicates is 'AD'
'ABDAADBDAABB' —> 'A B D
The idea is to recursively remove all adjacent duplicates in the string until no duplicates are left. This idea is inspired by Schlemiel painter’s algorithm and implemented below in C, C++, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <stdio.h> #include <string.h> // Function to remove all adjacent duplicates from the given string char* removeAdjDup(char* str, int n) { // base case if (n == 0) { return str; } // `k` maintains the index of the next free location in the result, // and `i` maintains the current index of the string int i, k = 0; int len = strlen(str); // start from the second character for (i = 1; i < len; i++) { // if the current character is not the same as the // previous character, add it to the 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 the last character to the result str[k++] = str[i - 1]; // null terminate the string str[k] = '\0'; // start again if any duplicate is removed if (k != n) { return removeAdjDup(str, k); // Schlemiel painter’s algorithm } // if the algorithm didn't change the input string, that means // all the adjacent duplicates are removed return str; } int main(void) { char str[] = "DBAABDAB"; int n = strlen(str); printf("The string left after the removal of all adjacent duplicates is %s", removeAdjDup(str, n)); return 0; } |
Output:
The string left after the removal of all adjacent duplicates is AB
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <string> using namespace std; // Function to remove all adjacent duplicates from the given string string removeAdjDup(string str) { int n = str.size(); // base case if (n == 0) { return str; } // `k` maintains the index of the next free location in the result, // and `i` maintains the current index of the string int i, k = 0; // start from the second character for (i = 1; i < n; i++) { // if the current character is not the same as the // previous character, add it to the result if (str[i - 1] != str[i]) { str[k++] = str[i - 1]; } else { // remove adjacent duplicates while (i < n && str[i - 1] == str[i]) { i++; } } } // add the last character to the result str[k++] = str[i - 1]; // start again if any duplicate is removed if (k != n) { return removeAdjDup(str.substr(0, k)); // Schlemiel painter’s algorithm } // if the algorithm didn't change the input string, that means // all the adjacent duplicates are removed return str.substr(0, k); } int main() { string str = "DBAABDAB"; cout << "The string left after the removal of all adjacent duplicates is " << removeAdjDup(str); return 0; } |
Output:
The string left after the removal of all adjacent duplicates is AB
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
class Main { // Function to remove all adjacent duplicates from the given string public static String removeAdjDup(String str) { // base case if (str == null || str.length() == 0) { return str; } char[] chars = str.toCharArray(); // `k` maintains the index of the next free location in the result, // and `i` maintains the current index of the string int i, k = 0; // start from the second character for (i = 1; i < chars.length; i++) { // if the current character is not the same as the // previous character, add it to the result if (chars[i - 1] != chars[i]) { chars[k++] = chars[i - 1]; } else { // remove adjacent duplicates while (i < chars.length && chars[i - 1] == chars[i]) { i++; } } } // add the last character to the result chars[k++] = chars[i - 1]; // construct a string with the first `k` chars String s = new String(chars).substring(0, k); // start again if any duplicate is removed if (k != chars.length) { return removeAdjDup(s); // Schlemiel painter’s algorithm } // if the algorithm didn't change the input string, that means // all the adjacent duplicates are removed return s; } public static void main(String[] args) { String str = "DBAABDAB"; System.out.println("The string left after the removal of all adjacent" + " duplicates is " + removeAdjDup(str)); } } |
Output:
The string left after the removal of all adjacent duplicates is AB
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# Function to remove all adjacent duplicates from the given string def removeAdjDup(s): chars = list(s) n = len(s) # `k` maintains the index of the next free location in the result k = 0 # `i` maintains the current index of the string i = 1 # start from the second character while i < n: # if the current character is not the same as the # previous character, add it to the result if chars[i - 1] != chars[i]: chars[k] = chars[i - 1] k = k + 1 else: # remove adjacent duplicates while i < len(chars) and chars[i - 1] == chars[i]: i = i + 1 i = i + 1 # add the last character to the result chars[k] = chars[i - 1] k = k + 1 # construct a string with the first `k` chars s = ''.join(chars[:k]) # start again if any duplicate is removed if k != n: return removeAdjDup(s) # Schlemiel painter’s algorithm # if the algorithm didn't change the input string, that means # all the adjacent duplicates are removed return s if __name__ == '__main__': s = 'DBAABDAB' print('The string left after removal of all adjacent duplicates is', removeAdjDup(s)) |
Output:
The string left after the removal of all adjacent duplicates is AB
The time complexity of the above solution is O(n2) since it might require (n+1)/2 passes in the worst case, where n is the length of the input string. The auxiliary space required by the program is O(n) for recursion (call stack).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)