Given a string S consisting of lowercase English alphabets, the task is to find the minimum number of characters required to be removed such that the characters of the string could be rearranged to form a palindrome.
Examples:
Input: S = “ababccca”
Output: 1
Explanation:
Remove the occurrence of ‘c’ from the string. Therefore, the modified string is “ababcca”, which can be rearranged to form the palindromic string “cababac”.
Therefore, only one removal is required.Input: S = abcde
Output: 4
Approach: The problem can be solved based on the observation that, in a palindromic string, at most one character can occur the odd number of times. Therefore, reduce the frequency of all odd-frequent characters except one of them.
Follow the steps below to solve the problem:
- Initialize an array of size 26 for storing the frequency of each character in S.
- Traverse the string
- Update the frequency of each character in the frequency array.
- Count the number of characters having an odd frequency and store it in a variable, say, count.
- If the count is 1 or 0, print 0 as the answer. Otherwise, print count – 1 as the answer.
Below is the implementation of the above approach:
C++
// C++ program for// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of deletions// required such that characters of the// string can be rearranged to form a palindromeint minDeletions(string str){ // Stores frequency of characters int fre[26]; memset(fre, 0, sizeof(fre)); int n = str.size();cout<<n; // Store the frequency of each // character in frequency array for (int i = 0; i < n; i++) { fre[str[i] - 'a'] += 1; } for (int i = 0; i < n; i++) { cout<<fre[i]; } int count = 0; // Count number of characters // with odd frequency for (int i = 0; i < 26; i++) { if (fre[i] % 2) { count += 1; } } // If count is 1 or 0, return 0 if (count == 0 || count == 1) { return 0; } // Otherwise, return count - 1 else { return count - 1; }}// Driver Codeint main(){ string str = "ababbccca"; // Function call to find minimum // number of deletions required cout << minDeletions(str) << endl;} |
Java
// Java program for the above approachpublic class GFG{ // Function to find the number of deletions // required such that characters of the // string can be rearranged to form a palindrome static int minDeletions(String str) { // Stores frequency of characters int fre[] = new int[26]; int n = str.length(); // Store the frequency of each // character in frequency array for (int i = 0; i < n; i++) { fre[str.charAt(i) - 'a'] += 1; } int count = 0; // Count number of characters // with odd frequency for (int i = 0; i < 26; i++) { if (fre[i] % 2 == 1) { count += 1; } } // If count is 1 or 0, return 0 if (count == 0 || count == 1) { return 0; } // Otherwise, return count - 1 else { return count - 1; } } // Driver Code public static void main (String[] args) { String str = "ababbccca"; // Function call to find minimum // number of deletions required System.out.println(minDeletions(str)) ; }}// This code is contributed by AnkThon |
Python3
# Python3 program for# the above approach# Function to find the number of deletions# required such that characters of the# string can be rearranged to form a palindromedef minDeletions(str): # Stores frequency of characters fre = [0]*26 # memset(fre, 0, sizeof(fre)); n = len(str) # Store the frequency of each # character in frequency array for i in range(n): fre[ord(str[i]) - ord('a')] += 1 count = 0 # Count number of characters # with odd frequency for i in range(26): if (fre[i] % 2): count += 1 # If count is 1 or 0, return 0 if (count == 0 or count == 1): return 0 # Otherwise, return count - 1 else: return count - 1# Driver Codeif __name__ == '__main__': str = "ababbccca" # Function call to find minimum # number of deletions required print (minDeletions(str)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the number of deletions // required such that characters of the // string can be rearranged to form a palindrome static int minDeletions(string str) { // Stores frequency of characters int []fre = new int[26]; int n = str.Length; // Store the frequency of each // character in frequency array for (int i = 0; i < n; i++) { fre[str[i] - 'a'] += 1; } int count = 0; // Count number of characters // with odd frequency for (int i = 0; i < 26; i++) { if (fre[i] % 2 == 1) { count += 1; } } // If count is 1 or 0, return 0 if (count == 0 || count == 1) { return 0; } // Otherwise, return count - 1 else { return count - 1; } } // Driver Code public static void Main(string[] args) { string str = "ababbccca"; // Function call to find minimum // number of deletions required Console.WriteLine(minDeletions(str)) ; }}// This code is contributed by AnkThon |
Javascript
<script>//Javascript program for// the above approach// Function to find the number of deletions// required such that characters of the// string can be rearranged to form a palindromefunction minDeletions(str){ // Stores frequency of characters var fre = new Array(26); fre.fill(0); var n = str.length; // Store the frequency of each // character in frequency array for (var i = 0; i < n; i++) { //let a = parseInt(str[i] - 97); fre[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; } var count = 0; // Count number of characters // with odd frequency for (var i = 0; i < 26; i++) { if (fre[i] % 2) { count += 1; } } // If count is 1 or 0, return 0 if (count == 0 || count == 1) { return 0; } // Otherwise, return count - 1 else { return count - 1; }} var str = "ababbccca"; // Function call to find minimum // number of deletions required document.write( minDeletions(str)+"<br>"); // This code is contributed by SoumikMondal</script> |
Output:
2
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!
