Given string str of lower case alphabets, the task is to output the minimum number of conversions to be made such that all characters are repeated an odd number of times, if the task is not possible, then print -1. Any alphabet can be converted into any other lower-case alphabet.
Examples:
Input: str = “neveropen”
Output: 2
Explanation: Convert one ‘g’ to ‘e’ and convert one ‘k’ to ‘s’Input: str = “neveropen”
Output: 1
Explanation: Convert ‘e’ to any character that is not present in the string
Approach: The given problem can be solved using a hashmap. The idea is to count the number of alphabets repeating an even number of times and storing their frequencies in the hashmap. The below approach can be followed to solve the problem:
- Iterate the string and put all characters in the hashmap:
- If the character is already present in the hashmap then increase its frequency by 1
- Iterate the hashmap and count the number of characters with even frequency and store it in a variable count
- If the value of count is:
- Even, then return count / 2
- Odd and the size of hashmap is:
- Less than 26 then return count / 2 + 1
- Equal to 26 then return -1
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to return minimum// number of conversions requiredint maxconv(string s){ // Declare a hashmap unordered_map<char, int> map; // Insert character into the map for (auto x : s) { // Increment the frequency of the // character present in the string map[x]++; } // Count to store number of even // frequency elements int count = 0; // Loop to calculate characters // with even frequency for (auto z : map) { // If frequency is even if (z.second % 2 == 0) // Increment the count count++; } // If characters with even // frequency are even if (count % 2 == 0) // return count / 2 as the answer return count / 2; // If characters with even // frequency are even are odd else if (count % 2 != 0) { // If map contains less than // 26 distinct characters if (map.size() < 26) { // Return count / 2 + 1 // as the answer return (count / 2) + 1; } else { // If map contains 26 // distinct characters return -1; } }}int main(){ // Initialize the string string s = "neveropen"; // Call the function and // print the output cout << maxconv(s) << "\n";} |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to return minimum // number of conversions required static int maxconv(String s) { // Declare a hashmap HashMap<Character, Integer> map = new HashMap<Character, Integer>(); // Converting given string to char array char[] strArray =s.toCharArray(); // Insert character into the map for (char c : strArray) { if (map.containsKey(c)) { // If char is present in charCountMap, // incrementing it's count by 1 map.put(c, map.get(c) + 1); } else { // If char is not present in charCountMap, // putting this char to charCountMap with 1 // as it's value map.put(c, 1); } } // Count to store number of even // frequency elements int count = 0; // Loop to calculate characters // with even frequency for (Map.Entry entry : map.entrySet()) { if ((int)entry.getValue() % 2 == 0) { // Increment the count count++; } } // If characters with even // frequency are even if ((count % 2) == 0) // return count / 2 as the answer return count / 2; // If characters with even // frequency are even are odd else if (count % 2 != 0) { // If map contains less than // 26 distinct characters if (map.size() < 26) { // Return count / 2 + 1 // as the answer return (count / 2) + 1; } else { // If map contains 26 // distinct characters return -1; } } return -1; } public static void main(String[] args) { // Initialize the string String s = "neveropen"; // Call the function and // print the output System.out.println(maxconv(s)); }}// This code is contributed by Potta Lokesh |
Python3
# python implementation for the above approach# Function to return minimum# number of conversions requireddef maxconv(s): # Declare a hashmap map = {} # Insert character into the map for x in s: # Increment the frequency of the # character present in the string if x in map: map[x] += 1 else: map[x] = 1 # Count to store number of even # frequency elements count = 0 # Loop to calculate characters # with even frequency for z in map: # If frequency is even if (map[z] % 2 == 0): # Increment the count count += 1 # If characters with even # frequency are even if (count % 2 == 0): # return count / 2 as the answer return count // 2 # If characters with even # frequency are even are odd elif (count % 2 != 0): # If map contains less than # 26 distinct characters if (len(map) < 26): # Return count / 2 + 1 # as the answer return (count // 2) + 1 else: # If map contains 26 # distinct characters return -1if __name__ == "__main__": # Initialize the string s = "neveropen" # Call the function and # print the output print(maxconv(s)) # This code is contributed by rakeshsahni |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to return minimum // number of conversions required static int maxconv(String s) { // Declare a hashmap Dictionary<char, int> map = new Dictionary<char, int>(); // Converting given string to char array char[] strArray = s.ToCharArray(); // Insert character into the map foreach (char c in strArray) { if (map.ContainsKey(c)) { // If char is present in charCountMap, // incrementing it's count by 1 map = map + 1; } else { // If char is not present in charCountMap, // putting this char to charCountMap with 1 // as it's value map = 1; } } // Count to store number of even // frequency elements int count = 0; // Loop to calculate characters // with even frequency foreach (int entry in map.Values) { if (entry % 2 == 0) { // Increment the count count++; } } // If characters with even // frequency are even if ((count % 2) == 0) // return count / 2 as the answer return count / 2; // If characters with even // frequency are even are odd else if (count % 2 != 0) { // If map contains less than // 26 distinct characters if (map.Count < 26) { // Return count / 2 + 1 // as the answer return (count / 2) + 1; } else { // If map contains 26 // distinct characters return -1; } } return -1; } public static void Main() { // Initialize the string String s = "neveropen"; // Call the function and // print the output Console.Write(maxconv(s)); }}// This code is contributed by gfgking |
Javascript
<script>// Javascript implementation for the above approach// Function to return minimum// number of conversions requiredfunction maxconv(s) { // Declare a hashmap let map = new Map(); // Insert character into the map for (x of s) { // Increment the frequency of the // character present in the string if (map.has(x)) { map.set(x, map.get(x) + 1) } else { map.set(x, 1) } } // Count to store number of even // frequency elements let count = 0; // Loop to calculate characters // with even frequency for (z of map) { // If frequency is even if (z[1] % 2 == 0) // Increment the count count++; } // If characters with even // frequency are even if (count % 2 == 0) // return count / 2 as the answer return Math.floor(count / 2); // If characters with even // frequency are even are odd else if (count % 2 != 0) { // If map contains less than // 26 distinct characters if (map.length < 26) { // Return count / 2 + 1 // as the answer return Math.floor(count / 2) + 1; } else { // If map contains 26 // distinct characters return -1; } }}// Initialize the stringlet s = "neveropen";// Call the function and// print the outputdocument.write(maxconv(s))// This code is contributed by gfgking.</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
