Given a string S, the task is to find the minimum removal of characters required such that the string S consists only of two alternating characters.
Examples:
Input: S = “adebbeeaebd”
Output: 7
Explanation: Removing all occurrences of ‘b’ and ‘e’ modifies the string to “adad”, which consist of alternating occurrences of ‘a’ and ‘d’.Input: S = “abccd”
Output: 3
Explanation: Removing all occurrences of ‘c’ and ‘d’ modifies the string to “ab”, which consist of alternating ‘a’ and ‘b’.
Approach: The problem can be solved by generating all the possible 262 pairs of English letters and find the pair with a maximum length of alternating occurrences, say len, in the string S. Then, print the number of characters required to be removed to achieve that by subtracting len from N.
Follow the steps below to solve the given problem:
- Initialize a variable, say len, to store the maximum length of alternating occurrences of a pair of characters.
- Iterate over every possible pair of English alphabets and for each pair, perform the following operations:
- Iterate over the characters of the string S and find the length, say newlen, of alternating occurrences of two characters from the string S.
- Check if len is smaller than newlen or not. If found to be true, then update len = newlen.
- Finally, print N – len as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// length of alternating occurrences// of a pair of characters in a string sint findLength(string s, char i, char j){ // Stores the next character // for alternating sequence char required = i; // Stores the length of alternating // occurrences of a pair of characters int length = 0; // Traverse the given string for (char curr : s) { // If current character is same // as the required character if (curr == required) { // Increase length by 1 length += 1; // Reset required character if (required == i) required = j; else required = i; } } // Return the length return length;}// Function to find minimum characters// required to be deleted from S to// obtain an alternating sequenceint minimumDeletions(string S){ // Stores maximum length // of alternating sequence // of two characters int len = 0; // Stores length of the string int n = S.length(); // Generate every pair // of English alphabets for (char i = 'a'; i <= 'z'; i++) { for (char j = i + 1; j <= 'z'; j++) { // Function call to find length // of alternating sequence for // current pair of characters int newLen = findLength(S, i, j); // Update len to store the maximum // of len and newLen in len len = max(len, newLen); } } // Return n - len as the final result return n - len;}// Driver Codeint main(){ // Given Input string S = "adebbeeaebd"; // Function call to find minimum // characters required to be removed // from S to make it an alternating // sequence of a pair of characters cout << minimumDeletions(S); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to find the maximum// length of alternating occurrences// of a pair of characters in a string sstatic int findLength(String s, char i, char j){ // Stores the next character // for alternating sequence char required = i; // Stores the length of alternating // occurrences of a pair of characters int length = 0; // Traverse the given string for(int k = 0; k < s.length(); k++) { char curr = s.charAt(k); // If current character is same // as the required character if (curr == required) { // Increase length by 1 length += 1; // Reset required character if (required == i) required = j; else required = i; } } // Return the length return length;}// Function to find minimum characters// required to be deleted from S to// obtain an alternating sequencestatic int minimumDeletions(String S){ // Stores maximum length // of alternating sequence // of two characters int len = 0; // Stores length of the string int n = S.length(); // Generate every pair // of English alphabets for(int i = 0; i < 26; i++) { for(int j = i + 1; j < 26; j++) { // Function call to find length // of alternating sequence for // current pair of characters int newLen = findLength(S, (char)(i + 97), (char)(j + 97)); // Update len to store the maximum // of len and newLen in len len = Math.max(len, newLen); } } // Return n - len as the final result return n - len;}// Driver Codepublic static void main (String[] args){ // Given Input String S = "adebbeeaebd"; // Function call to find minimum // characters required to be removed // from S to make it an alternating // sequence of a pair of characters System.out.print(minimumDeletions(S));}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find the maximum# length of alternating occurrences# of a pair of characters in a string sdef findLength(s, i, j): # Stores the next character # for alternating sequence required = i # Stores the length of alternating # occurrences of a pair of characters length = 0 # Traverse the given string for curr in s: # If current character is same # as the required character if (curr == required): # Increase length by 1 length += 1 # Reset required character if (required == i): required = j else: required = i # Return the length return length# Function to find minimum characters# required to be deleted from S to# obtain an alternating sequencedef minimumDeletions(S): # Stores maximum length # of alternating sequence # of two characters len1 = 0 # Stores length of the string n = len(S) # Generate every pair # of English alphabets for i in range(0, 26, 1): for j in range(i + 1, 26, 1): # Function call to find length # of alternating sequence for # current pair of characters newLen = findLength(S, chr(i + 97), chr(j + 97)) # Update len to store the maximum # of len and newLen in len len1 = max(len1, newLen) # Return n - len as the final result return n - len1# Driver Codeif __name__ == '__main__': # Given Input S = "adebbeeaebd" # Function call to find minimum # characters required to be removed # from S to make it an alternating # sequence of a pair of characters print(minimumDeletions(S))# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the maximum// length of alternating occurrences// of a pair of characters in a string sstatic int findLength(string s, char i, char j){ // Stores the next character // for alternating sequence char required = i; // Stores the length of alternating // occurrences of a pair of characters int length = 0; // Traverse the given string for(int k = 0; k < s.Length; k++) { char curr = s[k]; // If current character is same // as the required character if (curr == required) { // Increase length by 1 length += 1; // Reset required character if (required == i) required = j; else required = i; } } // Return the length return length;}// Function to find minimum characters// required to be deleted from S to// obtain an alternating sequencestatic int minimumDeletions(string S){ // Stores maximum length // of alternating sequence // of two characters int len = 0; // Stores length of the string int n = S.Length; // Generate every pair // of English alphabets for(int i = 0; i < 26; i++) { for(int j = i + 1; j < 26; j++) { // Function call to find length // of alternating sequence for // current pair of characters int newLen = findLength(S, (char)(i + 97), (char)(j + 97)); // Update len to store the maximum // of len and newLen in len len = Math.Max(len, newLen); } } // Return n - len as the final result return n - len;}// Driver Codepublic static void Main(string[] args){ // Given Input string S = "adebbeeaebd"; // Function call to find minimum // characters required to be removed // from S to make it an alternating // sequence of a pair of characters Console.WriteLine(minimumDeletions(S));}}// This code is contributed by avijitmondal1998 |
Javascript
<script>// JavaScript program for the above approach // Function to find the maximum// length of alternating occurrences// of a pair of characters in a string sfunction findLength( s, i, j){ // Stores the next character // for alternating sequence var required = i; // Stores the length of alternating // occurrences of a pair of characters let length = 0; // Traverse the given string for(let k = 0; k < s.length; k++) { var curr = s.charAt(k); // If current character is same // as the required character if (curr == required) { // Increase length by 1 length += 1; // Reset required character if (required == i) required = j; else required = i; } } // Return the length return length;}// Function to find minimum characters// required to be deleted from S to// obtain an alternating sequencefunction minimumDeletions( S){ // Stores maximum length // of alternating sequence // of two characters let len = 0; // Stores length of the string let n = S.length; // Generate every pair // of English alphabets for(let i = 0; i < 26; i++) { for(let j = i + 1; j < 26; j++) { // Function call to find length // of alternating sequence for // current pair of characters let newLen = findLength(S, String.fromCharCode(i + 97), String.fromCharCode(j + 97)); // Update len to store the maximum // of len and newLen in len len = Math.max(len, newLen); } } // Return n - len as the final result return n - len;}// Driver Code// Given Inputlet S = "adebbeeaebd"; // Function call to find minimum// characters required to be removed// from S to make it an alternating// sequence of a pair of charactersdocument.write(minimumDeletions(S)); </script> |
Output:
7
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
