Given string str consisting of lowercase letters, the task is to find the minimum number of characters to be deleted from the given string such that any permutation of the remaining string is a palindrome.
Examples:
Input: str=aba
Output: 1
Explanation: Removing b generates a palindromic string aa.Input: abab
Output: 0
Explanation: Permutations abba, baab of the given string are already palindrome. Therefore, no character needs to be deleted.Input: abab
Output: 0
Approach: Follow the steps below to solve the problem:
- Check if the given string is already a palindrome or not. If found to be true, print 0.
- Otherwise, calculate the frequency of each character in the string using a Hashmap.
- Count the number of characters with odd frequencies and store it in a variable, say k.
- Now, the total number of characters required to be deleted is k-1. Therefore, print k %u2013 1 as the required answer.
Below is the implementation of the above approach:
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a string
// is palindrome or not
bool IsPalindrome(string& str)
{
string s = str;
// Reverse the string
reverse(str.begin(), str.end());
// Check if the string is
// already a palindrome or not
if (s == str) {
return true;
}
return false;
}
// Function to calculate the minimum
// deletions to make a string palindrome
void CountDeletions(string& str, int len)
{
if (IsPalindrome(str)) {
cout << 0 << endl;
return;
}
// Stores the frequencies
// of each character
map<char, int> mp;
// Iterate over the string
for (int i = 0; i < len; i++) {
// Update frequency of
// each character
mp[str[i]]++;
}
int k = 0;
// Iterate over the map
for (auto it : mp) {
// Count characters with
// odd frequencies
if (it.second & 1) {
k++;
}
}
// Print the result
cout << k - 1 << endl;
}
int main()
{
string str = "abca";
int len = str.length();
CountDeletions(str, len);
}
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Comments