Wednesday, 27 Oct 2021

# Minimum removals required such that given string consists only of a pair of alternating characters

Minimum removals required such that given string consists only of a pair of alternating characters
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: 7Explanation: 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: 3Explanation: 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 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 occurences 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++

#include
using namespace std;

int findLength(string s, char i, char j)
{

char required = i;

int length = 0;

for (char curr : s) {

if (curr == required) {

length += 1;

if (required == i)
required = j;
else
required = i;
}
}

return length;
}

int minimumDeletions(string S)
{

int len = 0;

int n = S.length();

for (char i = ‘a’; i