5

Find minimum operations to make all characters of a string identical

 1 year ago
source link: https://www.geeksforgeeks.org/find-minimum-operations-to-make-all-characters-of-a-string-identical/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Find minimum operations to make all characters of a string identical

Given a string of size N, the task is to find the minimum operation required in a string such that all elements of a string are the same. In one operation, you can choose at least one character from the string and remove all chosen characters from the string, but you can’t choose an adjacent character from the string.

Examples:

Input: string = “geeks”
Output: 2
Explanation: 

  • In one operation, you will remove elements at index 1 and 4. Now the string is “ees”,
  • In the second operation, you will remove the element at index 3.

Input: string = “xyabcdadb”
Output: 2
Explanation: 

  • In one operation, you will remove elements at indexes 1, 4, 6, and 8. Now the string is “yacab”,
  • In the second operation, you will remove elements at index 1, 3, and 5.

Approach: To solve the problem follow the below idea:

We will iterate from key = ‘a’ to ‘z’ and we will erase all elements except the key. For every key, we will find the length of the maximum subarray that doesn’t contain the current key. we will take the minimum from all maximum subarray lengths from a to z. Now our aim is to remove all elements from the subarray because we remove all elements from the maximum subarray for a particular key, then we can easily remove all subarray that length is less than or equal to the maximum subarray length in the same operation. Now, we will choose an element from the min length subarray such that no adjacent element is chosen and remove it and it will take a total Log2x+1 operation, where x is the length of the minimum subarray. We can find the answer also by dividing x by 2 until it is not zero and increasing the answer by 1 when we divide.

Below are the steps to implement the above idea:

  • We will iterate the key from char- ‘a’ to ‘z’.
  • Now we will find the maximum subarray length that doesn’t contain the current key for every key from ‘a’ to ‘z’.
  • Then, we will take the minimum subarray length from all maximum subarray for a key from ‘a’ to ‘z’.
  • Now, we have to remove all elements from the minimum length subarray.
  • Then, we will divide the subarray length by 2 until it becomes zero and increase the answer by 1 when we divide.
  • Finally, print the final answer.

Below is the implementation of the above approach:

// C++ code for the above approach:

#include <bits/stdc++.h>
using namespace std;

// Function to find minimum operation
// required in a string such that all
// elements become same after performing
// operation in a string
int makeequal(string s, int n)
{
    int minsubarray, ans = 0;

    // Iterating all lower case alphabets
    for (int j = 0; j < 26; j++) {

        // Current lower case alphabet
        char key = 'a' + j;
        int temp = 0, ma = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == key) {

                // Updating maximum
                // length of subarray
                ma = max(ma, temp);

                // That doesn't contain
                // current key
                temp = 0;
            }
            else {

                temp += 1;
            }
            if (i == n - 1) {
                ma = max(ma, temp);
            }
        }

        minsubarray = min(minsubarray, ma);

        // Taking minimum length subarray
        // from maximum subarray length
        // for each key from 'a' to 'z'.
    }

    // Dividing minsubarray by 2
    // until it is not zero
    while (minsubarray != 0) {
        ans += 1;
        minsubarray = minsubarray / 2;
    }

    // Return the answer
    return ans;
}

// Drive code
int main()
{
    string s = "xyabcdadb";
    int n = s.size();

    // Function call
    cout << makeequal(s, n);

    return 0;
}
Output
2

Time Complexity: O(26*N)
Auxiliary Space: O(1)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK