Given a string S of length N. The task is to find the minimum number of steps required on strings, so that it has exactly K different alphabets all with the same frequency.
Note: In one step, we can change a letter to any other letter.
Examples:
Input: S = "abbc", N = 4, K = 2 Output: 1 In one step convert 'c' to 'a'. Hence string has two different letters a and b both occurring 2 times.
Approach:
- Check if K divides N, then only it is possible to convert the given string, otherwise not.
- Maintain the count of all alphabets present in string S, in an array A.
- Evaluate E = N/K, the frequency with which alphabets will be present in the final string.
- Separate the alphabets with frequency more than or equal to E and less than E in two parts.
- Maintain the number of steps required for each alphabet to convert its count to E, sort these vector obtained in above step.
- Lastly, take all possibility to pick:
Set 1 : 0 Set 2 : K Set 1 : 1 Set 2 : K-1 .... so on
- Keep a ans variable to calculate minimum number of steps among all possibility in step 6.
- Say L1 is the number of operation required on Set 1, L2 is the number of operations required on set 2. Then total operations required is maximum of L1, L2 . As suppose ‘a’ is required one less in string while ‘b’ is required one more than we can change ‘a’ to ‘b’, thus reducing number of steps.
Below is the implementation of the above approach:
C++
// C++ program to convert the given string#include <bits/stdc++.h>using namespace std;// Function to find the minimum number of// operations to convert the given stringvoid minOperation(string S, int N, int K){ // Check if N is divisible by K if (N % K) { cout << "Not Possible" << endl; return; } // Array to store frequency of characters // in given string int count[26] = { 0 }; for (int i = 0; i < N; i++) { count[S[i] - 97]++; } int E = N / K; vector<int> greaterE; vector<int> lessE; for (int i = 0; i < 26; i++) { // Two arrays with number of operations // required if (count[i] < E) lessE.push_back(E - count[i]); else greaterE.push_back(count[i] - E); } sort(greaterE.begin(), greaterE.end()); sort(lessE.begin(), lessE.end()); int mi = INT_MAX; for (int i = 0; i <= K; i++) { // Checking for all possibility int set1 = i; int set2 = K - i; if (greaterE.size() >= set1 && lessE.size() >= set2) { int step1 = 0; int step2 = 0; for (int j = 0; j < set1; j++) step1 += greaterE[j]; for (int j = 0; j < set2; j++) step2 += lessE[j]; mi = min(mi, max(step1, step2)); } } cout << mi << endl;}// Driver Codeint main(){ string S = "accb"; int N = S.size(); int K = 2; minOperation(S, N, K); return 0;} |
Java
// JAVA program to convert the given stringimport java.util.*;class GFG{ // Function to find the minimum number of // operations to convert the given string static void minOperation(String S, int N, int K) { // Check if N is divisible by K if (N % K != 0) { System.out.println("Not Possible"); } else { // Array to store frequency of characters // in given string int [] count = new int[26]; for (int i = 0; i < N; i++) { count[(S.charAt(i) - 97)]++; } int E = N / K; Vector<Integer> greaterE = new Vector<>(); Vector<Integer> lessE = new Vector<>(); for (int i = 0; i < 26; i++) { // Two arrays with number of operations // required if (count[i] < E) lessE.add(E - count[i]); else greaterE.add(count[i] - E); } Collections.sort(greaterE); Collections.sort(lessE); int mi = Integer.MAX_VALUE; for (int i = 0; i <= K; i++) { // Checking for all possibility int set1 = i; int set2 = K - i; if (greaterE.size() >= set1 && lessE.size() >= set2) { int step1 = 0; int step2 = 0; for (int j = 0; j < set1; j++) step1 += greaterE.get(j); for (int j = 0; j < set2; j++) step2 += lessE.get(j); mi = Math.min(mi, Math.max(step1, step2)); } } System.out.println(mi); } } // Driver Code public static void main (String[] args) { String S = "accb"; int N = S.length(); int K = 2; minOperation(S, N, K); }}// This code is contributed by ihritik |
Python3
# Python3 program to convert the given string # Function to find the minimum number of # operations to convert the given string def minOperation(S, N, K): # Check if N is divisible by K if N % K: print("Not Possible") return # Array to store frequency of # characters in given string count = [0] * 26 for i in range(0, N): count[ord(S[i]) - 97] += 1 E = N // K greaterE = [] lessE = [] for i in range(0, 26): # Two arrays with number of # operations required if count[i] < E: lessE.append(E - count[i]) else: greaterE.append(count[i] - E) greaterE.sort() lessE.sort() mi = float('inf') for i in range(0, K + 1): # Checking for all possibility set1, set2 = i, K - i if (len(greaterE) >= set1 and len(lessE) >= set2): step1, step2 = 0, 0 for j in range(0, set1): step1 += greaterE[j] for j in range(0, set2): step2 += lessE[j] mi = min(mi, max(step1, step2)) print(mi) # Driver Code if __name__ == "__main__": S = "accb" N = len(S) K = 2 minOperation(S, N, K) # This code is contributed by Rituraj Jain |
C#
// C# program to convert the given stringusing System;using System.Collections.Generic;class GFG{ // Function to find the minimum number of // operations to convert the given string static void minOperation(string S, int N, int K) { // Check if N is divisible by K if (N % K != 0) { Console.WriteLine("Not Possible"); } else { // Array to store frequency of characters // in given string int [] count = new int[26]; for (int i = 0; i < N; i++) { count[(S[i] - 97)]++; } int E = N / K; List<int> greaterE = new List<int>(); List<int> lessE = new List<int>(); for (int i = 0; i < 26; i++) { // Two arrays with number of operations // required if (count[i] < E) lessE.Add(E - count[i]); else greaterE.Add(count[i] - E); } greaterE.Sort(); lessE.Sort(); int mi = Int32.MaxValue; for (int i = 0; i <= K; i++) { // Checking for all possibility int set1 = i; int set2 = K - i; if (greaterE.Count >= set1 && lessE.Count >= set2) { int step1 = 0; int step2 = 0; for (int j = 0; j < set1; j++) step1 += greaterE[j]; for (int j = 0; j < set2; j++) step2 += lessE[j]; mi = Math.Min(mi, Math.Max(step1, step2)); } } Console.WriteLine(mi); } } // Driver Code public static void Main () { string S = "accb"; int N = S.Length; int K = 2; minOperation(S, N, K); }}// This code is contributed by ihritik |
Javascript
<script>// Javascript program to convert the given string// Function to find the minimum number of// operations to convert the given stringfunction minOperation(S, N, K){ // Check if N is divisible by K if (N % K) { document.write( "Not Possible" ); return; } // Array to store frequency of characters // in given string var count = Array(26).fill(0); for (var i = 0; i < N; i++) { count[S[i].charCodeAt(0) - 97]++; } var E = N / K; var greaterE = []; var lessE = []; for (var i = 0; i < 26; i++) { // Two arrays with number of operations // required if (count[i] < E) lessE.push(E - count[i]); else greaterE.push(count[i] - E); } greaterE.sort(); lessE.sort(); var mi = 1000000000; for (var i = 0; i <= K; i++) { // Checking for all possibility var set1 = i; var set2 = K - i; if (greaterE.length >= set1 && lessE.length >= set2) { var step1 = 0; var step2 = 0; for (var j = 0; j < set1; j++) step1 += greaterE[j]; for (var j = 0; j < set2; j++) step2 += lessE[j]; mi = Math.min(mi, Math.max(step1, step2)); } } document.write( mi );}// Driver Codevar S = "accb";var N = S.length;var K = 2;minOperation(S, N, K);</script> |
Output:
1
Time Complexity: O(1) As the value of k is constant so it is neglected in time complexity.
Auxiliary Space: O(1) As we are taking a constant space of size 26.
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!
