Two Pointer Approach
- Take two pointers i and j where i is the pointer for the original string and j is the pointer of new string.
- traverse the original string character by character.
- if the current character is same as the last character in the new string, remove the last character from the new string.
- otherwise, add the current character to the new string.
- finally, remove the remaining characters from the new string. if string is empty at this point, return -1.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h> using namespace std; string reduceString(string s) { int n = s.size(); int j = 0; // pointer for the new string for ( int i = 0; i < n; i++) { if (j > 0 && s[i] == s[j-1]) { j--; // remove the last character from the new string } else { s[j++] = s[i]; // add the current character to the new string } } s.erase(j); // remove the remaining characters from the new string if (s.empty()) return "-1" ; return s; } int main() { string s= "aaabbaaccd" ; cout << reduceString(s) << endl; return 0; } |
Java
// Nikunj Sonigara public class Main { public static String reduceString(String s) { int n = s.length(); int j = 0 ; // pointer for the new string char [] result = new char [n]; // create a character array to store the new string for ( int i = 0 ; i < n; i++) { if (j > 0 && s.charAt(i) == result[j - 1 ]) { j--; // remove the last character from the new string } else { result[j++] = s.charAt(i); // add the current character to the new string } } return new String(result, 0 , j); // convert the character array to a string } public static void main(String[] args) { String s = "aaabbaaccd" ; String reducedString = reduceString(s); if (reducedString.isEmpty()) { System.out.println( "-1" ); } else { System.out.println(reducedString); } } } |
Python3
# Nikunj Sonigara def reduceString(s): n = len (s) j = 0 # pointer for the new string result = [''] * n # create a list to store the new string for i in range (n): if j > 0 and s[i] = = result[j - 1 ]: j - = 1 # remove the last character from the new string else : result[j] = s[i] # add the current character to the new string j + = 1 return ''.join(result[:j]) # convert the list to a string if __name__ = = "__main__" : s = "aaabbaaccd" reduced_string = reduceString(s) if not reduced_string: print ( "-1" ) else : print (reduced_string) |
C#
// C# Code using System; class GFG { static string ReduceString( string s) { int n = s.Length; int j = 0; // pointer for the new string char [] newString = new char [n]; for ( int i = 0; i < n; i++) { if (j > 0 && s[i] == newString[j - 1]) { j--; // remove the last character from the new string } else { newString[j++] = s[i]; // add the current character to the new string } } // Create a new string with the characters we kept string reducedString = new string (newString, 0, j); if ( string .IsNullOrEmpty(reducedString)) { return "-1" ; } return reducedString; } static void Main() { string s = "aaabbaaccd" ; Console.WriteLine(ReduceString(s)); } } // This code is contributed by guptapratik |
Javascript
// Javascript code function reduceString(s) { const n = s.length; let j = 0; // pointer for the new string const newString = new Array(n); for (let i = 0; i < n; i++) { if (j > 0 && s[i] === newString[j - 1]) { j--; // remove the last character from the new string } else { newString[j++] = s[i]; // add the current character to the new string } } // Create a new string with the characters we kept const reducedString = newString.slice(0, j).join( '' ); if (reducedString.length === 0) { return "-1" ; } return reducedString; } // Example usage: const s = "aaabbaaccd" ; console.log(reduceString(s)); // This code is contributed by guptapratik |
ad
Time Complexity: O(n)
Auxiliary Space: O(1)
String with minimum length after applying given conditions
Our geek loves to play with strings, Currently, he is trying to reduce the size of a string by recursively removing all the consecutive duplicate pairs. In other words, He can apply the below operations any number of times. Remove all the consecutive duplicate pairs and concatenate the remaining string to replace the original string.
Find the string with minimum length after applying the above operations.
Note: If the string length becomes zero after applying operations, return “-1” as a string.
Examples:
Input: aaabbaaccd
Output: ad
Explanation:
Remove (aa)abbaaccd =>abbaaccd
Remove a(bb)aaccd => aaaccd
Remove (aa)accd => accd
Remove a(cc)d => adInput: aaaa
Output: -1
Explanation:
Remove (aa)aa => aa
Again removing the pair of duplicates then (aa) will be removed and we will get ‘Empty String’.
Approach: This can be solved with the following idea:
Running a loop allows you to easily compare the current element with its predecessor. You must utilize a data structure (Stack) where you can push from the rear and pop from the front for this.
Steps involved in the implementation of code:
- Stack is the ideal data structure to employ in this situation.
- Execute a loop across the elements of the array.
- If the stack is empty or the element at the top is not the same as the element in the array that is currently being iterated, just push the element to the stack.
- You may quickly remove the top element of the stack if the top element and the currently selected element are the same, as this meets the requirement stated in the problem statement.
- The elements in the stack that are still there after the iteration will produce the desired results.
- The element must be reversed and placed in a string. This will be the response we provide.
Below is the implementation of the code:
C++
#include <iostream> #include <stack> using namespace std; string removePair(string s) { stack< char > res; res.push(s[0]); int curr_idx = 1; while (curr_idx < s.length()) { if (res.empty() || s[curr_idx] != res.top()) res.push(s[curr_idx]); else res.pop(); curr_idx++; } string ans = "" ; while (!res.empty()) { ans = res.top() + ans; res.pop(); } if (ans.empty()) ans = "-1" ; return ans; } int main() { string inputString = "aaabbaaccd" ; // Function call cout << removePair(inputString) << endl; return 0; } //This code is contributed by ayush pathak |
Java
// Java code for the above approach: import java.util.*; class GFG { // Function to reomve duplicates // from string public static String removePair(String s) { // Intialise stack data structure Stack<Character> res = new Stack<>(); res.add(s.charAt( 0 )); int curr_idx = 1 ; while (curr_idx < s.length()) { // If stack is empty if (res.size() == 0 ) res.add(s.charAt(curr_idx)); else if (s.charAt(curr_idx) == res.peek()) res.pop(); else res.add(s.charAt(curr_idx)); // Increment in index curr_idx += 1 ; } String ans = "" ; // Concat the characters // in string ans for ( char k : res) ans += Character.toString(k); if (ans.length() == 0 ) ans = "-1" ; return ans; } // Driver Code public static void main(String[] args) { String inputString = "aaabbaaccd" ; // Function call System.out.println(removePair(inputString)); } } |
Python3
# Python3 code for the above approach: # Function to reomve duplicates # from string def remove_pair(s): res = [] res.append(s[ 0 ]) curr_idx = 1 while curr_idx < len (s): if not res or s[curr_idx] ! = res[ - 1 ]: res.append(s[curr_idx]) else : res.pop() # Increment in index curr_idx + = 1 ans = "" # Concat the characters # in string ans while res: ans = res.pop() + ans if not ans: ans = "-1" return ans # Driver code if __name__ = = "__main__" : # input string input_string = "aaabbaaccd" # Function call print (remove_pair(input_string)) |
C#
using System; using System.Collections.Generic; public class Program { public static string RemovePair( string s) { Stack< char > res = new Stack< char >(); res.Push(s[0]); int curr_idx = 1; while (curr_idx < s.Length) { if (res.Count == 0 || s[curr_idx] != res.Peek()) res.Push(s[curr_idx]); else res.Pop(); curr_idx++; } string ans = "" ; while (res.Count > 0) { ans = res.Peek() + ans; res.Pop(); } if (ans == "" ) ans = "-1" ; return ans; } public static void Main() { string inputString = "aaabbaaccd" ; // Function call Console.WriteLine(RemovePair(inputString)); } } |
Javascript
// JavaScript code for the above approach: // Function to reomve duplicates // from string function removePair(s) { // Create a stack to store the characters of the string let res = [s[0]]; let currIdx = 1; // Iterate through the string from second character to end while (currIdx < s.length) { // If the stack is empty or the current character is not // same as the top of stack then push the current character // into the stack if (res.length === 0 || s[currIdx] !== res[res.length - 1]) { res.push(s[currIdx]); } // Else pop the top of stack else { res.pop(); } // Increment in index currIdx++; } // If the stack is empty, return -1 if (res.length === 0) { return "-1" ; } else { return res.join( "" ); } } // Driver Code const inputString = "aaabbaaccd" ; // Function Call console.log(removePair(inputString)); |
ad
Time Complexity: O(N)
Auxiliary Space: O(N) as we are using an extra stack data structure
Approach:
- Initialize an empty string to store the reduced string.
- Iterate through the characters of the input string from left to right.
- For each character, check if it matches the next character. If it does, skip the next character as it forms a consecutive duplicate pair with the current character. Otherwise, append the current character to the reduced string.
- After iterating through all characters, the reduced string will contain the remaining characters of the input string after removing all consecutive duplicate pairs.
- If the reduced string is empty, it means all characters were removed, and we return “-1” as the output. Otherwise, return the reduced string.
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; string removePair(string s) { string result = "" ; // String to store reduced string int n = s.length(); for ( int i = 0; i < n;) { if (s[i] == s[i + 1]) { i += 2; // Skip next character if it forms consecutive duplicate pair } else { result += s[i]; // Append current character to reduced string i++; // Move to next character } } if (result.empty()) return "-1" ; // Return "-1" if reduced string is empty else return result; // Return the reduced string } int main() { string inputString = "aaabbaaccd" ; // Function call cout << removePair(inputString) << endl; return 0; } |
Java
public class Main { public static String removePair(String s) { StringBuilder result = new StringBuilder(); // StringBuilder to store reduced string int n = s.length(); for ( int i = 0 ; i < n;) { if (i < n - 1 && s.charAt(i) == s.charAt(i + 1 )) { i += 2 ; // Skip next character if it forms consecutive duplicate pair } else { result.append(s.charAt(i)); // Append current character to reduced string i++; // Move to next character } } if (result.length() == 0 ) return "-1" ; // Return "-1" if reduced string is empty else return result.toString(); // Return the reduced string } public static void main(String[] args) { String inputString = "aaabbaaccd" ; // Function call System.out.println(removePair(inputString)); } } // This code is contributed by Vikram_Shirsat |
Python3
def removePair(s): # String to store reduced string result = "" n = len (s) i = 0 while i + 1 < n: if s[i] = = s[i + 1 ]: # Skip next character if it forms consecutive duplicate pair i + = 2 else : # Append current character to reduced string result + = s[i] # Move to next character i + = 1 # If last element is left and unique append in result if s[i] ! = s[i - 1 ]: result + = s[i] if result = = "": # Return "-1" if reduced string is empty return "-1" else : # Return the reduced string return result # Driver code inputString = "aaabbaaccd" print (removePair(inputString)) |
C#
using System; class Program { // Function to remove consecutive duplicate pairs from a string static string RemovePair( string s) { string result = "" ; // String to store reduced string int n = s.Length; for ( int i = 0; i < n;) { if (i + 1 < n && s[i] == s[i + 1]) { i += 2; // Skip next character if it forms consecutive duplicate pair } else { result += s[i]; // Append current character to reduced string i++; // Move to next character } } if ( string .IsNullOrEmpty(result)) return "-1" ; // Return "-1" if the reduced string is empty else return result; // Return the reduced string } // Main method static void Main() { string inputString = "aaabbaaccd" ; // Function call Console.WriteLine(RemovePair(inputString)); } } |
Javascript
function removePair(s) { // String to store reduced string let result = "" ; let n = s.length; for (let i = 0; i < n;) { // Skip next character if it forms consecutive duplicate pair if (s[i] === s[i + 1]) { i += 2; } else { // Append current character to reduced string result += s[i]; // Move to next character i++; } } // Return "-1" if reduced string is empty if (result === "" ) { return "-1" ; } // Return the reduced string else { return result; } } // Test case let inputString = "aaabbaaccd" ; console.log(removePair(inputString)); |
Output:
ad
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), as we are not using any extra space.