Given a string Str, the task is to remove first adjacent pairs of similar characters until we can.
Note: Remove adjacent characters to get a new string and then again remove adjacent duplicates from the new string and keep repeating this process until all similar adjacent character pairs are removed.
Examples:
Input: str = “keexxllx”
Output: kx
Step 0: Remove ee to get “kxxllx”
Step 1: Remove xx to get “kllx”
Step 2: Remove ll to get “kx”
Input: str = “abbaca”
Output: ca
Approach:
Use string’s back() and pop_back() method STL in C++ to solve the above problem. Iterate for every character in the string, and if the adjacent characters are same, then remove the adjacent characters using pop_back() function. At the end, return the final string.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to remove adjacent duplicatesstring removeDuplicates(string S){ string ans = ""; // Iterate for every character // in the string for (auto it : S) { // If ans string is empty or its last // character does not match with the // current character then append this // character to the string if (ans.empty() or ans.back() != it) ans.push_back(it); // Matches with the previous one else if (ans.back() == it) ans.pop_back(); } // Return the answer return ans;}// Driver Codeint main(){ string str = "keexxllx"; cout << removeDuplicates(str);} |
Java
// Java implementation of the above approachclass GFG { // Function to remove adjacent duplicates static String removeDuplicates(String S) { String ans = ""; // Iterate for every character // in the string for (int i = 0; i < S.length(); i++) { // If ans string is empty or its last // character does not match with the // current character then append this // character to the string if (ans.isEmpty() || ans.charAt(ans.length() - 1) != S.charAt(i)) ans += S.charAt(i); // Matches with the previous one else if (ans.charAt(ans.length() - 1) == S.charAt(i)) ans = ans.substring(0, ans.length() - 1); } // Return the answer return ans; } // Driver Code public static void main(String[] args) { String str = "keexxllx"; System.out.println(removeDuplicates(str)); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the above approach # Function to remove adjacent duplicates def removeDuplicates(S) : ans = ""; # Iterate for every character # in the string for it in S : # If ans string is empty or its last # character does not match with the # current character then append this # character to the string if (ans == "" or ans[-1] != it) : ans += it ; # Matches with the previous one elif (ans[-1] == it) : ans = ans[:-1]; # Return the answer return ans; # Driver Code if __name__ == "__main__" : string = "keexxllx"; print(removeDuplicates(string)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approachusing System; class GFG { // Function to remove adjacent duplicates static String removeDuplicates(String S) { String ans = ""; // Iterate for every character // in the string for (int i = 0; i < S.Length; i++) { // If ans string is empty or its last // character does not match with the // current character then append this // character to the string if (ans == "" || ans[ans.Length - 1] != S[i]) ans += S[i]; // Matches with the previous one else if (ans[ans.Length - 1] == S[i]) ans = ans.Substring(0, ans.Length - 1); } // Return the answer return ans; } // Driver Code public static void Main(String[] args) { String str = "keexxllx"; Console.WriteLine(removeDuplicates(str)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the above approach// Function to remove adjacent duplicates function removeDuplicates( S) { var ans = ""; // Iterate for every character // in the string for (i = 0; i < S.length; i++) { // If ans string is empty or its last // character does not match with the // current character then append this // character to the string if (ans.length==0 || ans.charAt(ans.length - 1) != S.charAt(i)) ans += S.charAt(i); // Matches with the previous one else if (ans.charAt(ans.length - 1) == S.charAt(i)) ans = ans.substring(0, ans.length - 1); } // Return the answer return ans; } // Driver Code var str = "keexxllx"; document.write(removeDuplicates(str));// This code contributed by Rajput-Ji</script> |
kx
Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the length of the string.
Auxiliary Space: O(N), as we are using extra space for the ans string. Where N is the length of the string.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
