Minimizing Operations to Prevent Palindrome Formation
Given a string S of length N (N >= 2). You can choose any index and replace the character at that index with any other character of your choice any number of times, then the task is to minimize the number of operations (including zero), after that, all the characters can’t make an S palindrome when arranged optimally.
Note: It is always possible to make S non-palindrome by a finite number of operations.
Examples:
Input: N = 3, S = “xux”
Output: 1
Explanation: Replace the first character with ‘z’, So the S becomes “zux”. It can be verified that now all the characters of S can’t be arranged to form a palindrome. So only 1 operation is needed. Therefore, output is 1.Input: N = 4, S = “abxy”
Output: 0
Explanation: S already contains characters such that they can’t make S palindrome when arranged optimally. So, 0 operations are required. Therefore output 0.
Approach: To solve the problem follow the below idea:
The problem can be solved by using HashMap data structure. We need to count the number of occurrence of each distinct character. For more clarification see the Concept of Approach section below.
Concept of Approach:
First initialize a HashMap let say map for counting the frequencies of distinct characters. For solving this problem, we must clear with the important point that S can be palindrome only and only if there is at most one odd frequency in map.
For Example:
- “abaxx” can be arranged to form palindrome as “axbxa” because we have 1 odd frequency (character ‘b’).
- “aaabbc” can’t be arranged to form palindrome. Because we have 2 odd frequencies (character ‘b’).
So, we have to focus on making odd frequencies in map greater than 1. Therefore, count the parity of frequencies in the variables let say even and odd.
There can be following cases in map:
- If map has size equal to 1:
- If S has even size:
- For example: “aaaa”. replace any one character with ‘z’ gives S as “aaaz”. Now it can’t be arranged to form palindrome. Therefore, only 1 operation is required.
- If S has odd size:
- For example: “aaaaa”. replace any two initial characters with two different characters let say ‘b’ and ‘c’ gives S as “aaabc”. Now it can’t be arranged to form palindrome. Therefore, only 2 operations are required.
- If map has size equal to 2:
- If both frequencies are odd:
- In this case, S can’t be arranged to from palindrome. Therefore, 0 operation required.
- If both frequencies are even:
- In this case, convert an even frequency by using 1 operation into 2 odd frequencies. For example: “aabb”, replace an occurrence of ‘b’ with ‘x’, So, S becomes “aabx”. Therefore, only 1 operation is required.
- If one frequency is even and one is odd:
- In this case also 1 operation is required, same as above.
- If map has size greater than 2:
- If odd frequencies are >=2:
- No operations as S can’t be arranged to form palindrome.
- Else:
- Only 1 operation is required. Which converts an even frequency into two odd frequencies.
Steps to implement above idea:
- Initialize a HashMap let say map for storing frequencies.
- Create two variables Even and Odd for counting even and odd frequencies respectively.
- Store frequencies in map by traversing on S using loop.
- Traverse map, count odd and even frequencies and store them into Odd and Even respectively.
- Return minimum operations by following given conditions:
- If (map.size() == 1):
- If S.length() is even then return 1 else return 2.
- If (map.size() == 2):
- If (Odd==2) return 0 else return 1.
- Else
- If (Odd >=2) return 0 else return 1.
- If (map.size() == 1):
Code to implement the approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; int MinimumOperations( int n, string s) { // Initializing a hashmap unordered_map< char , int > mp; // Traversing the string 's' to store frequencies in the // map for ( int i = 0; i < n; i++) { char x = s[i]; mp[x] = mp[x] + 1; } // Odd and Even variables for counting Odd and Even // frequencies stored in the map int odd = 0; int even = 0; // Traversing the map for counting odd and even // frequencies for ( auto & it : mp) { if (it.second % 2 == 0) { even++; } else { odd++; } } // If size of map is 1 if (mp.size() == 1) { return (n % 2 == 0 ? 1 : 2); } // If size of map is 2 else if (mp.size() == 2) { if (odd == 2) return 0; else if (even == 2) return 1; else if (odd == 1 && even == 1) return 1; } // If size of map is > 2 else { if (odd >= 2) return 0; else return 1; } return 0; } int main() { // Inputs int N = 5; string S = "xyjyj" ; // Function call and printing output cout << MinimumOperations(N, S) << endl; return 0; } // This code is contributed by Abhinav Mahajan (abhinav_m22) |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver Function public static void main(String[] args) throws java.lang.Exception { // Inputs int N = 5 ; String S = "xyjyj"; // Function call and printing output System.out.println(MinimumOperations(N, S)); } // Function for returning minimum operations public static int MinimumOperations( int n, String s) { // Initializing HashMap HashMap<Character, Integer> map = new HashMap<>(); // Traversing on S for storing // frequencies in map for ( int i = 0 ; i < s.length(); i++) { char x = s.charAt(i); map.put(x, map.getOrDefault(x, 0 ) + 1 ); } // Odd and Even variables for counting // Odd and Even frequencies stored in map int odd = 0 ; int even = 0 ; // Traversing on map // for counting odd and even frequncies for (Map.Entry<Character, Integer> set : map.entrySet()) { if (set.getValue() % 2 == 0 ) { even++; } else { odd++; } } // If size of map is 1 if (map.size() == 1 ) { return (n % 2 == 0 ? 1 : 2 ); } // If size of map is 2 else if (map.size() == 2 ) { if (odd == 2 ) return 0 ; else if (even == 2 ) return 1 ; else if (odd == 1 && even == 1 ) return 1 ; } // If size of map is > 2 else { if (odd >= 2 ) return 0 ; else return 1 ; } return 0 ; } } |
Python3
# Python code to implement the approach # Function for returning minimum operations def MinimumOperations(n, s): # Initializing dictionary dictionary = {} # Traversing on S for storing # frequencies in dictionary for i in range ( len (s)): x = s[i] dictionary[x] = dictionary.get(x, 0 ) + 1 # Odd and Even variables for counting # Odd and Even frequencies stored in dictionary odd = 0 even = 0 # Traversing on dictionary # for counting odd and even frequencies for key, value in dictionary.items(): if value % 2 = = 0 : even + = 1 else : odd + = 1 # If size of dictionary is 1 if len (dictionary) = = 1 : return 1 if n % 2 = = 0 else 2 # If size of dictionary is 2 elif len (dictionary) = = 2 : if odd = = 2 : return 0 elif even = = 2 : return 1 elif odd = = 1 and even = = 1 : return 1 # If size of dictionary is > 2 else : if odd > = 2 : return 0 else : return 1 return 0 # Driver Function if __name__ = = "__main__" : # Inputs N = 5 S = "xyjyj" # Function call and printing output print (MinimumOperations(N, S)) # This code is contributed by Sakshi |
C#
using System; using System.Collections.Generic; class Program { static int MinimumOperations( int n, string s) { // Initializing a dictionary Dictionary< char , int > mp = new Dictionary< char , int >(); // Traversing the string 's' to store frequencies in the map for ( int i = 0; i < n; i++) { char x = s[i]; if (mp.ContainsKey(x)) { mp[x]++; } else { mp[x] = 1; } } // Odd and Even variables for counting Odd and Even frequencies stored in the map int odd = 0; int even = 0; // Traversing the dictionary for counting odd and even frequencies foreach ( var kvp in mp) { if (kvp.Value % 2 == 0) { even++; } else { odd++; } } // If size of map is 1 if (mp.Count == 1) { return (n % 2 == 0) ? 1 : 2; } // If size of map is 2 else if (mp.Count == 2) { if (odd == 2) return 0; else if (even == 2) return 1; else if (odd == 1 && even == 1) return 1; } // If size of map is > 2 else { if (odd >= 2) return 0; else return 1; } return 0; } static void Main() { // Inputs int N = 5; string S = "xyjyj" ; // Function call and printing output Console.WriteLine(MinimumOperations(N, S)); } } //Contributed by Aditi Tyagi |
Javascript
// JavaScript code for the above approach function minimumOperations(n, s) { // Initializing a map object const mp = new Map(); // Traversing the string 's' to store frequencies in the map for (let i = 0; i < n; i++) { const x = s[i]; mp.set(x, (mp.get(x) || 0) + 1); } // Variables for counting odd and even frequencies let odd = 0; let even = 0; // Traversing the map for counting odd and even frequencies for (let [key, value] of mp) { if (value % 2 === 0) { even++; } else { odd++; } } // If size of map is 1 if (mp.size === 1) { return n % 2 === 0 ? 1 : 2; } // If size of map is 2 else if (mp.size === 2) { if (odd === 2) { return 0; } else if (even === 2) { return 1; } else if (odd === 1 && even === 1) { return 1; } } // If size of map is > 2 else { if (odd >= 2) { return 0; } else { return 1; } } return 0; } // Inputs const N = 5; const S = "xyjyj" ; // Function call and printing output console.log(minimumOperations(N, S)); |
1
Time Complexity: O(N)
Auxiliary Space: O(N), As HashMap is used to store frequencies.
Contact Us