Minimum number of removals required such that no subsequence of length 2 occurs more than once
Given a string S consisting of N lowercase characters, the task is to modify the given string such that no subsequence of length two repeats in the string by removing minimum number of characters.
Examples:
Input: S = “abcaadbcd”
Output: abcd
Explanation: Removing the characters at indices {2, 3, 4, 5, 6, 7} modifies the string to “abcd”, that contains every subsequence of length 2 exactly once.Input: S = “cadbcc”
Output: cadbc
Approach: The given problem can be solved based on the observation that the final string can contain only unique characters with the exception that the first character can occur 2 times in the string, one at the start and the other at the end(if possible). Follow the steps below to solve the problem:
- Initialize an empty string, say ans to store the resultant final string.
- Initialize a boolean array C[] of size 26 to check if the character is present in the final string or not.
- Initialize a variable, say pos as 0 to store the index of the last character added to the string, ans.
- Traverse the given string S and if the current character is not present in ans, then append it to ans, mark it as visited in the array C[], and update the value of pos to i.
- Iterate over the range [pos + 1, N – 1] using the variable i and if S[i] is equal to S[0], then append it to the final string ans and break out of the loop.
- After completing the above steps, print the string ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to remove the minimum count // of characters from the string such // that no subsequence of length 2 repeats void RemoveCharacters(string s) { // Initialize the final string string ans = "" ; // Stores if any character occurs // in the final string or not bool c[26]; for ( int i = 0; i < 26; i++) c[i] = 0; // Store the index of the last // character added in the string int pos = 0; // Traverse the string for ( int i = 0; i < s.size(); i++) { // Add all the unique // characters if (c[s[i] - 'a' ] == 0) { c[s[i] - 'a' ] = 1; pos = i; ans += s[i]; } } // Check if S[0] appears in the // range [pos+1, N-1] for ( int i = pos + 1; i < ( int )s.size(); i++) { // If the characters are the // same if (s[i] == s[0]) { ans += s[i]; break ; } } // Print the resultant string cout << ans; } // Driver Code int main() { string S = "abcaadbcd" ; RemoveCharacters(S); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to remove the minimum count // of characters from the string such // that no subsequence of length 2 repeats static void RemoveCharacters(String s) { // Initialize the final string String ans = "" ; // Stores if any character occurs // in the final string or not int []c = new int [ 26 ]; for ( int i = 0 ; i < 26 ; i++) c[i] = 0 ; // Store the index of the last // character added in the string int pos = 0 ; // Traverse the string for ( int i = 0 ; i < s.length(); i++) { // Add all the unique // characters if (c[( int )s.charAt(i) - 97 ] == 0 ) { c[( int )s.charAt(i) - 97 ] = 1 ; pos = i; ans += s.charAt(i); } } // Check if S[0] appears in the // range [pos+1, N-1] for ( int i = pos + 1 ; i < s.length(); i++) { // If the characters are the // same if (s.charAt(i) == s.charAt( 0 )) { ans += s.charAt(i); break ; } } // Print the resultant string System.out.println(ans); } // Driver code public static void main(String[] args) { String S = "abcaadbcd" ; RemoveCharacters(S); } } // This code is contributed by code_hunt. |
Python3
# Python 3 program for the above approach # Function to remove the minimum count # of characters from the string such # that no subsequence of length 2 repeats def RemoveCharacters(s): # Initialize the final string ans = "" # Stores if any character occurs # in the final string or not c = [ 0 for i in range ( 26 )] # Store the index of the last # character added in the string pos = 0 # Traverse the string for i in range ( len (s)): # Add all the unique # characters if (c[ ord (s[i]) - 97 ] = = 0 ): c[ ord (s[i]) - 97 ] = 1 pos = i ans + = s[i] # Check if S[0] appears in the # range [pos+1, N-1] for i in range (pos + 1 , len (s), 1 ): # If the characters are the # same if (s[i] = = s[ 0 ]): ans + = s[i] break # Print the resultant string print (ans) # Driver Code if __name__ = = '__main__' : S = "abcaadbcd" RemoveCharacters(S) # This code is contributed by ipg2016107. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to remove the minimum count // of characters from the string such // that no subsequence of length 2 repeats static void RemoveCharacters( string s) { // Initialize the final string string ans = "" ; // Stores if any character occurs // in the final string or not int []c = new int [26]; for ( int i = 0; i < 26; i++) c[i] = 0; // Store the index of the last // character added in the string int pos = 0; // Traverse the string for ( int i = 0; i < s.Length; i++) { // Add all the unique // characters if (c[( int )s[i] - 97] == 0) { c[( int )s[i] - 97] = 1; pos = i; ans += s[i]; } } // Check if S[0] appears in the // range [pos+1, N-1] for ( int i = pos + 1; i < s.Length; i++) { // If the characters are the // same if (s[i] == s[0]) { ans += s[i]; break ; } } // Print the resultant string Console.Write(ans); } // Driver Code public static void Main() { string S = "abcaadbcd" ; RemoveCharacters(S); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // javascript program for the above approach // Function to remove the minimum count // of characters from the string such // that no subsequence of length 2 repeats function RemoveCharacters(s) { // Initialize the final string var ans = "" ; // Stores if any character occurs // in the final string or not var c = new Array(26); var i; for (i = 0; i < 26; i++) c[i] = 0; // Store the index of the last // character added in the string var pos = 0; // Traverse the string for (i = 0; i < s.length; i++) { // Add all the unique // characters if (c[s[i].charCodeAt() - 97] == 0) { c[s[i].charCodeAt() - 97] = 1; pos = i; ans += s[i]; } } // Check if S[0] appears in the // range [pos+1, N-1] for (i = pos + 1; i < s.length; i++) { // If the characters are the // same if (s[i] == s[0]) { ans += s[i]; break ; } } // Print the resultant string document.write(ans); } // Driver Code var S = "abcaadbcd" ; RemoveCharacters(S); // This code is contributed by bgangwar59. </script> |
abcd
Time Complexity: O(N)
Auxiliary Space: O(N)