Removing Subsequence from concatenated Array

Given array A[] formed by the concatenation of string “ABC” one or multiple times. The task for this problem is to remove all occurrences of subsequence “ABC” by performing the following operation a minimum number of times. In one operation swap any two elements of array A[]. print the number of operations required and elements on which operations are performed in each step.

Examples:

Input: A[] = {‘A’, ‘B’, ‘C’}
Output: 1
1 3
Explanation: Swapping 1’st and 3’rd element of array A[] it becomes A[] = {‘C’, ‘B’, ‘A’} which does not contain “ABC’” as subsequence.

Input: A[] = {‘A’, ‘B’, ‘C’, ‘A’, ‘B’, ‘C’};
Output: 1
1 6

Approach: To solve the problem follow the below idea:

No subsequences of string “ABC” would also mean no substrings of “ABC” in array A[]. it would be also be the lower bound for having no subsequences of string “ABC”.

Swap i-th A from start with i-th C from end for 1 <= i <= ceil(N / 6) We can see that, no substrings of “ABC” exists after performing ceil(N / 6) operations. Since we can only destroy atmost 2 substrings in one operations, ceil(N / 6) is minimum possible. Now if you see clearly, after performing above operations, there does not exist any subsequence of string ABC in original string. Hence ceil(N / 6)  is also the answer for the original problem.

Below are the steps for the above approach:

• Create variable numberOfOperations.
• Create two pointers L = 1 and R = N.
• Create an array eachStep[][2] to store which elements will be replaced at which step.
• Run a while loop till L < R.
• Each step push {L, R} to eachStep[][2] then move pointer L to 3 steps forwards and R to 3 steps backward.
• After while loop ends print the numberOfOperations and eachStep[][2] array.

Below is the implementation of the above approach:

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;

// Function to remove every occurence of
// subsequence ABC by peforming
// minimum number of swaps
void minimizeOperations(char A[], int N)
{

    // Variable that stores nunber of
    // operations required
    int numberOfOperations = ceil(N / 2.0);

    // Left and Right pointer of array
    int L = 1, R = N;

    // To store answer of each step
    vector<pair<int, int> > eachStep;

    // Store operation on each step
    while (L < R) {

        // L and R will be swaped
        // in next step
        eachStep.push_back({ L, R });

        // Move pointers for next operation
        L += 3;
        R -= 3;
    }

    // Printing number of operations
    cout << numberOfOperations << endl;

    // Each step of operation
    for (auto ans : eachStep)
        cout << ans.first << " " << ans.second << endl;

    // Next line
    cout << endl
         << endl;
}

// Driver Code
int32_t main()
{

    // Input 1
    int N = 3;
    char A[] = { 'A', 'B', 'C' };

    // Function Call
    minimizeOperations(A, N);

    // Input 2
    int N1 = 6;
    char A1[] = { 'A', 'B', 'C', 'A', 'B', 'C' };

    // Function Call
    minimizeOperations(A1, N1);

    return 0;
}

Time Complexity: O(N)  
Auxiliary Space: O(N)         

Given array A[] formed by the concatenation of string “ABC” one or multiple times. The task for this problem is to remove all occurrences of subsequence “ABC” by performing the following operation a minimum number of times. In one operation swap any two elements of array A[]. print the number of operations required and elements on which operations are performed in each step.

Examples:

Input: A[] = {‘A’, ‘B’, ‘C’}
Output: 1
1 3
Explanation: Swapping 1’st and 3’rd element of array A[] it becomes A[] = {‘C’, ‘B’, ‘A’} which does not contain “ABC’” as subsequence.

Input: A[] = {‘A’, ‘B’, ‘C’, ‘A’, ‘B’, ‘C’};
Output: 1
1 6

Approach: To solve the problem follow the below idea:

No subsequences of string “ABC” would also mean no substrings of “ABC” in array A[]. it would be also be the lower bound for having no subsequences of string “ABC”.

Swap i-th A from start with i-th C from end for 1 <= i <= ceil(N / 6) We can see that, no substrings of “ABC” exists after performing ceil(N / 6) operations. Since we can only destroy atmost 2 substrings in one operations, ceil(N / 6) is minimum possible. Now if you see clearly, after performing above operations, there does not exist any subsequence of string ABC in original string. Hence ceil(N / 6)  is also the answer for the original problem.

Below are the steps for the above approach:

• Create variable numberOfOperations.
• Create two pointers L = 1 and R = N.
• Create an array eachStep[][2] to store which elements will be replaced at which step.
• Run a while loop till L < R.
• Each step push {L, R} to eachStep[][2] then move pointer L to 3 steps forwards and R to 3 steps backward.
• After while loop ends print the numberOfOperations and eachStep[][2] array.

Below is the implementation of the above approach:

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;

// Function to remove every occurence of
// subsequence ABC by peforming
// minimum number of swaps
void minimizeOperations(char A[], int N)
{

    // Variable that stores nunber of
    // operations required
    int numberOfOperations = ceil(N / 2.0);

    // Left and Right pointer of array
    int L = 1, R = N;

    // To store answer of each step
    vector<pair<int, int> > eachStep;

    // Store operation on each step
    while (L < R) {

        // L and R will be swaped
        // in next step
        eachStep.push_back({ L, R });

        // Move pointers for next operation
        L += 3;
        R -= 3;
    }

    // Printing number of operations
    cout << numberOfOperations << endl;

    // Each step of operation
    for (auto ans : eachStep)
        cout << ans.first << " " << ans.second << endl;

    // Next line
    cout << endl
         << endl;
}

// Driver Code
int32_t main()
{

    // Input 1
    int N = 3;
    char A[] = { 'A', 'B', 'C' };

    // Function Call
    minimizeOperations(A, N);

    // Input 2
    int N1 = 6;
    char A1[] = { 'A', 'B', 'C', 'A', 'B', 'C' };

    // Function Call
    minimizeOperations(A1, N1);

    return 0;
}

Time Complexity: O(N)  
Auxiliary Space: O(N)