Given a string str containing lowercase characters, the task is to find the minimum number of operations needed to make all the characters equal. In one operation, any consonant can be converted to any vowel or any vowel can be converted to any consonant.
Examples:
Input: str = “banana”
Output: 3
Explanation: Convert all consonants to Vowel character AInput: str = “hexon”
Output: 5
Explanation: Convert E to O first then all the consonants to Alphabet O
Approach: The basic catch here is that:
- The operations required to change a consonant to another consonant or a vowel to another vowel: 2 Operation
- The operation required to change a consonant to a vowel or a vowel to consonant: 1 Operation
So, it’s clear that it is more economical to change a consonant to a vowel or a vowel to a consonant than changing a consonant to another consonant or a vowel to another vowel.
Now to solve this question, follow the steps below:
- Calculate the frequency of all the characters and find the consonant and vowels with the highest frequency, let’s say A and B respectively.
- Try to change all the characters to A and B, and store the operations required in variables minA and minB respectively.
- Minimum of minA and minB is the answer to this problem.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum operations// required to make all string characters equalint minOperations(string str){ int n = str.size(); // Vector to store the // frequency of all characters vector<int> freq(26, 0); for (auto x : str) { freq[x - 'a']++; } int mxA = INT_MIN, mxB = INT_MIN; // Variables to store // consonant and vowel // with highest frequency char A, B; vector<char> vowels = { 'a', 'e', 'i', 'o', 'u' }; for (int i = 0; i < 26; ++i) { bool isVowel = 0; for (auto x : vowels) { if ('a' + i == x) { isVowel = 1; break; } } // If current character is a vowel if (isVowel) { if (mxB < freq[i]) { mxB = freq[i]; B = 'a' + i; } } // If current character is a consonant else { if (mxA < freq[i]) { mxA = freq[i]; A = 'a' + i; } } } int minA = 0, minB = 0; for (auto x : str) { bool isVowel = 0; for (auto y : vowels) { if (x == y) { isVowel = 1; break; } } // If current character is a vowel if (isVowel) { if (x != B) { minB += 2; } minA += 1; } // If current character is a // consonant else { if (x != A) { minA += 2; } minB += 1; } } // If no vowel exists if (mxB == INT_MIN) { return minA; } // If no consonant exists if (mxA == INT_MIN) { return minB; } // Returning minimum of the two return min(minA, minB);}// Driver Codeint main(){ string str = "hexon"; cout << minOperations(str);} |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Function to return the minimum operations // required to make all string characters equal static int minOperations(String str) { int n = str.length(); // Vector to store the // frequency of all characters char[] freq = new char[26]; for(char x : str.toCharArray()) { freq[x - 'a']++; } int mxA = Integer.MIN_VALUE, mxB = Integer.MIN_VALUE; // Variables to store // consonant and vowel // with highest frequency char A = ' ', B = ' '; char[] vowels = { 'a', 'e', 'i', 'o', 'u' }; for (int i = 0; i < 26; ++i) { int isVowel = 0; for(char x : vowels) { if ('a' + i == x) { isVowel = 1; break; } } // If current character is a vowel if (isVowel > 0) { if (mxB < freq[i]) { mxB = freq[i]; B = (char)(97 + i); } } // If current character is a consonant else { if (mxA < freq[i]) { mxA = freq[i]; A = (char)(97 + i); } } } int minA = 0, minB = 0; for(char x : str.toCharArray()) { int isVowel = 0; for(char y : vowels) { if (x == y) { isVowel = 1; break; } } // If current character is a vowel if (isVowel > 0) { if (x != B) { minB += 2; } minA += 1; } // If current character is a // consonant else { if (x != A) { minA += 2; } minB += 1; } } // If no vowel exists if (mxB == Integer.MIN_VALUE) { return minA; } // If no consonant exists if (mxA == Integer.MIN_VALUE) { return minB; } // Returning minimum of the two return Math.min(minA, minB); } // Driver Code public static void main(String args[]) { String str = "hexon"; System.out.println(minOperations(str)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# python program for the above approachINT_MIN = -2147483647 - 1# Function to return the minimum operations# required to make all string characters equaldef minOperations(str): n = len(str) # Vector to store the # frequency of all characters freq = [0 for _ in range(26)] for x in str: freq[ord(x) - ord('a')] += 1 mxA = INT_MIN mxB = INT_MIN # Variables to store # consonant and vowel # with highest frequency A = '' B = '' vowels = ['a', 'e', 'i', 'o', 'u'] for i in range(0, 26): isVowel = 0 for x in vowels: if (ord('a') + i == ord(x)): isVowel = 1 break # If current character is a vowel if (isVowel): if (mxB < freq[i]): mxB = freq[i] B = chr(ord('a') + i) # If current character is a consonant else: if (mxA < freq[i]): mxA = freq[i] A = chr(ord('a') + i) minA = 0 minB = 0 for x in str: isVowel = 0 for y in vowels: if (x == y): isVowel = 1 break # If current character is a vowel if (isVowel): if (x != B): minB += 2 minA += 1 # If current character is a # consonant else: if (x != A): minA += 2 minB += 1 # If no vowel exists if (mxB == INT_MIN): return minA # If no consonant exists if (mxA == INT_MIN): return minB # Returning minimum of the two return min(minA, minB)# Driver Codeif __name__ == "__main__": str = "hexon" print(minOperations(str)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG { // Function to return the minimum operations // required to make all string characters equal static int minOperations(string str) { int n = str.Length; // Vector to store the // frequency of all characters char[] freq = new char[26]; foreach(char x in str) { freq[x - 'a']++; } int mxA = Int32.MinValue, mxB = Int32.MinValue; // Variables to store // consonant and vowel // with highest frequency char A = ' ', B = ' '; char[] vowels = { 'a', 'e', 'i', 'o', 'u' }; for (int i = 0; i < 26; ++i) { int isVowel = 0; foreach(char x in vowels) { if ('a' + i == x) { isVowel = 1; break; } } // If current character is a vowel if (isVowel > 0) { if (mxB < freq[i]) { mxB = freq[i]; B = (char)(97 + i); } } // If current character is a consonant else { if (mxA < freq[i]) { mxA = freq[i]; A = (char)(97 + i); } } } int minA = 0, minB = 0; foreach(char x in str) { int isVowel = 0; foreach(char y in vowels) { if (x == y) { isVowel = 1; break; } } // If current character is a vowel if (isVowel > 0) { if (x != B) { minB += 2; } minA += 1; } // If current character is a // consonant else { if (x != A) { minA += 2; } minB += 1; } } // If no vowel exists if (mxB == Int32.MinValue) { return minA; } // If no consonant exists if (mxA == Int32.MinValue) { return minB; } // Returning minimum of the two return Math.Min(minA, minB); } // Driver Code public static void Main() { string str = "hexon"; Console.WriteLine(minOperations(str)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to return the minimum operations// required to make all string characters equalfunction minOperations(str) { let n = str.length; // Vector to store the // frequency of all characters let freq = new Array(26).fill(0); for (x of str) { freq[x.charCodeAt(0) - 'a'.charCodeAt(0)]++; } let mxA = Number.MIN_SAFE_INTEGER, mxB = Number.MIN_SAFE_INTEGER; // Variables to store // consonant and vowel // with highest frequency let A = "", B = ""; let vowels = ['a', 'e', 'i', 'o', 'u']; for (let i = 0; i < 26; ++i) { let isVowel = 0; for (x of vowels) { if ('a'.charCodeAt(0) + i == x.charCodeAt(0)) { isVowel = 1; break; } } // If current character is a vowel if (isVowel) { if (mxB < freq[i]) { mxB = freq[i]; B = String.fromCharCode('a'.charCodeAt(0) + i); } } // If current character is a consonant else { if (mxA < freq[i]) { mxA = freq[i]; A = String.fromCharCode('a'.charCodeAt(0) + i); } } } let minA = 0, minB = 0; for (x of str) { let isVowel = 0; for (y of vowels) { if (x == y) { isVowel = 1; break; } } // If current character is a vowel if (isVowel) { if (x != B) { minB += 2; } minA += 1; } // If current character is a // consonant else { if (x != A) { minA += 2; } minB += 1; } } // If no vowel exists if (mxB == Number.MIN_SAFE_INTEGER) { return minA; } // If no consonant exists if (mxA == Number.MIN_SAFE_INTEGER) { return minB; } // Returning minimum of the two return Math.min(minA, minB);}// Driver Codelet str = "hexon";document.write(minOperations(str))// This code is contributed by saurabh_jaiswal.</script> |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
- Iterate over each character in the input string and count the number of vowels and consonants separately.
- If either the vowel count or consonant count is zero, return 0 because all characters are already equal.
- If the vowel count and consonant count are equal, return either count since any character can be converted to the other.
- Otherwise, return the minimum of the vowel count and consonant count multiplied by 2, plus 1 to account for the remaining characters that need to be converted to the opposite type.
- This minimum count represents the minimum number of operations needed to make all characters in the string equal.
Below is the implementation of the above approach:
C++
#include <iostream>#include <string>#include <algorithm>bool isVowel(char c) { c = tolower(c); return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');}int minOperationsToMakeAllCharactersEqual(const std::string& str) { int vowelCount = 0; int consonantCount = 0; for (char c : str) { if (isVowel(c)) { vowelCount++; } else { consonantCount++; } } if (vowelCount == 0 || consonantCount == 0) { return 0; // All characters are already equal } if (vowelCount == consonantCount) { return vowelCount; // Both vowels and consonants are equal, any character can be converted to the other } return std::min(vowelCount, consonantCount) * 2 + 1;}int main() { std::string str = "hexon"; int minOperations = minOperationsToMakeAllCharactersEqual(str); std::cout << minOperations << std::endl; return 0;}// This code is contributed by rudra1807raj |
Java
//Java program to implement above approachimport java.util.HashSet;public class Main { // Function to check if a character is a vowel private static boolean isVowel(char c) { c = Character.toLowerCase(c); // Using HashSet to efficiently check if the character is a vowel HashSet<Character> vowels = new HashSet<>(); vowels.add('a'); vowels.add('e'); vowels.add('i'); vowels.add('o'); vowels.add('u'); return vowels.contains(c); } // Function to calculate the minimum number of operations // to make all characters in the string equal private static int minOperationsToMakeAllCharactersEqual(String string) { int vowelCount = 0; int consonantCount = 0; // Counting the number of vowels and consonants in the string for (char c : string.toCharArray()) { if (isVowel(c)) { vowelCount++; } else { consonantCount++; } } // All characters are already equal (either all vowels or all consonants) if (vowelCount == 0 || consonantCount == 0) { return 0; } // Both vowels and consonants are equal, any character can be converted to the other if (vowelCount == consonantCount) { return vowelCount; } // Return the minimum of vowelCount and consonantCount multiplied by 2 plus 1 return Math.min(vowelCount, consonantCount) * 2 + 1; } // Driver code public static void main(String[] args) { String string = "hexon"; int minOperations = minOperationsToMakeAllCharactersEqual(string); System.out.println(minOperations); }} |
Python3
# Python3 program for the above approachdef is_vowel(c): c = c.lower() return c in ['a', 'e', 'i', 'o', 'u']def min_operations_to_make_all_characters_equal(string): vowel_count = 0 consonant_count = 0 for c in string: if is_vowel(c): vowel_count += 1 else: consonant_count += 1 if vowel_count == 0 or consonant_count == 0: return 0 # All characters are already equal if vowel_count == consonant_count: return vowel_count # Both vowels and consonants are equal, any character can be converted to the other return min(vowel_count, consonant_count) * 2 + 1# Driver codeif __name__ == '__main__': string = "hexon" min_operations = min_operations_to_make_all_characters_equal(string) print(min_operations) |
C#
//C# code for the above approachusing System;class Program{ // Function to check if a character is a vowel static bool IsVowel(char c) { c = char.ToLower(c); return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'); } // Function to calculate the minimum operations needed to make all characters equal static int MinOperationsToMakeAllCharactersEqual(string str) { int vowelCount = 0; int consonantCount = 0; foreach (char c in str) { if (IsVowel(c)) { vowelCount++; } else { consonantCount++; } } if (vowelCount == 0 || consonantCount == 0) { return 0; // All characters are already equal } if (vowelCount == consonantCount) { return vowelCount; // Both vowels and consonants are equal, any character can be converted to the other } return Math.Min(vowelCount, consonantCount) * 2 + 1; } static void Main() { string str = "hexon"; int minOperations = MinOperationsToMakeAllCharactersEqual(str); Console.WriteLine(minOperations); }} |
Javascript
//Javascript program to implement above approach// Function to check if a character is a vowelfunction isVowel(c) { c = c.toLowerCase(); return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');}// Function to calculate the minimum number of operations// to make all characters in the string equalfunction minOperationsToMakeAllCharactersEqual(str) { let vowelCount = 0; let consonantCount = 0;// Counting the number of vowels and consonants in the string for (let c of str) { if (isVowel(c)) { vowelCount++; } else { consonantCount++; } }// All characters are already equal (either all vowels or all consonants) if (vowelCount == 0 || consonantCount == 0) { return 0; // All characters are already equal }// Both vowels and consonants are equal, any character can be converted to the other if (vowelCount == consonantCount) { return vowelCount; // Both vowels and consonants are equal, any character can be converted to the other } return Math.min(vowelCount, consonantCount) * 2 + 1;}let str = "hexon";let minOperations = minOperationsToMakeAllCharactersEqual(str);console.log(minOperations); |
Output
5
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!
