检查是否可以通过删除最多K个字符来使给定字符串的排列为回文
给定字符串str和整数K，任务是通过从给定字符串中删除最多K个字符，检查给定字符串的排列是否可以变为回文。
示例：
输入：
str = "geeksforgeeks", K = 2输出：
Yes说明：
移除给定字符串中的（
str[5]，str[6]）使其余字符串"geeksrgeeks"为回文。 因此，所需的输出是Yes。输入：
str = "coder", K = 1输出：
No
方法：可以使用哈希解决问题。 想法是遍历给定字符串的字符，并存储给定字符串的每个不同字符的频率。 如果给定字符串具有奇数频率的不同字符数小于或等于K + 1，则打印Yes。 否则，打印No。 请按照以下步骤解决问题：
-
初始化数组，例如说
cntFreq[]，以存储str的每个字符的频率。 -
初始化一个变量，例如说
cntOddFreq，以存储给定字符串的不同字符的计数，其频率为奇数。 -
遍历
cntFreq[]数组并检查cntFreq[i] % 2 == 1，然后将cntOddFreq的值增加1。 -
最后，检查
cntOddFreq ≤ (K + 1)，然后打印True。 -
否则，打印
False。
下面是上述方法的实现：
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if
// the string satisfies
// the given conditions or not
bool checkPalinK(string str, int K)
{
// Stores length of
// given string
int N = str.length();
// Stores frequency of
// each character of str
int cntFreq[256] = { 0 };
for (int i = 0; i < N;
i++) {
// Update frequency of
// current character
cntFreq[str[i]]++;
}
// Stores count of
// distinct character
// whose frequency is odd
int cntOddFreq = 0;
// Traverse the cntFreq[]
// array.
for (int i = 0; i < 256;
i++) {
// If frequency of
// character i is odd
if (cntFreq[i] % 2
== 1) {
// Update cntOddFreq
cntOddFreq++;
}
}
// If count of distinct character
// having odd frequency is <= K + 1
if (cntOddFreq <= (K + 1)) {
return true;
}
return false;
}
// Driver Code
int main()
{
string str = "geeksforgeeks";
int K = 2;
// If str satisfy
// the given conditions
if (checkPalinK(str, K)) {
cout << "Yes";
}
else {
cout << "No";
}
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to check if
// the string satisfies
// the given conditions or not
public static boolean checkPalinK(String str,
int K)
{
// Stores length of
// given string
int N = str.length();
// Stores frequency of
// each character of str
int cntFreq[] = new int[257];
for(int i = 0; i < N; i++)
{
// Update frequency of
// current character
cntFreq[str.charAt(i)]++;
}
// Stores count of
// distinct character
// whose frequency is odd
int cntOddFreq = 0;
// Traverse the cntFreq[]
// array.
for(int i = 0; i < 256; i++)
{
// If frequency of
// character i is odd
if (cntFreq[i] % 2 == 1)
{
// Update cntOddFreq
cntOddFreq++;
}
}
// If count of distinct character
// having odd frequency is <= K + 1
if (cntOddFreq <= (K + 1))
{
return true;
}
return false;
}
// Driver Code
public static void main(String args[])
{
String str = "geeksforgeeks";
int K = 2;
// If str satisfy
// the given conditions
if (checkPalinK(str, K))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by hemanth gadarla
输出：
Yes
时间复杂度：O(N + 256)，其中N是给定字符串的长度。
辅助空间：O(256)。
版权属于：月萌API www.moonapi.com，转载请注明出处
