Dada una string str y un entero K , la tarea es verificar si una permutación de la string dada se puede convertir en un palindrómico eliminando como máximo K caracteres de la string dada.
Ejemplos:
Entrada: str = “geeksforgeeks”, K = 2
Salida: Sí
Explicación:
Eliminar (str[5], str[6]) de la string dada hace que la string restante “geeksrgeeks” sea palindrómica. Por lo tanto, la salida requerida es Sí.Entrada: str = “codificador”, K = 1
Salida: No
Enfoque: El problema se puede resolver usando Hashing . La idea es iterar sobre los caracteres de la string dada y almacenar la frecuencia de cada carácter distinto de la string dada . Si el recuento de caracteres distintos de la string dada que tiene una frecuencia impar es menor o igual a (K + 1) , imprima Sí . De lo contrario , imprima No. Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos cntFreq[] para almacenar la frecuencia de cada carácter de str .
- Recorra la string dada y almacene la frecuencia de cada carácter distinto de la string str en la array cntFreq[] .
- Inicialice una variable, digamos cntOddFreq para almacenar el recuento de caracteres distintos de la string dada cuya frecuencia es un número impar.
- Recorra la array cntFreq[] y compruebe si cntFreq[i] % 2 == 1 y luego incremente el valor de cntOddFreq en 1 .
- Finalmente, verifique si cntOddFreq ≤ (K + 1) y luego imprima True .
- De lo contrario, imprime Falso .
A continuación se muestra la implementación del enfoque anterior:
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[256];
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
Python3
# Python3 program to implement
# the above approach
# Function to check if the
# satisfies the given
# conditions or not
def checkPalinK(str, K):
# Stores length of
# given string
N = len(str)
# Stores frequency of
# each character of str
cntFreq = [0] * 256
for i in range(N):
# Update frequency of
# current character
cntFreq[ord(str[i])] += 1
# Stores count of
# distinct character
# whose frequency is odd
cntOddFreq = 0
# Traverse the cntFreq[]
# array.
for i in range(256):
# If frequency of
# character i is odd
if (cntFreq[i] % 2 == 1):
# Update cntOddFreq
cntOddFreq += 1
# If count of distinct character
# having odd frequency is <= K + 1
if (cntOddFreq <= (K + 1)):
return True
return False
# Driver Code
if __name__ == '__main__':
str = "geeksforgeeks"
K = 2
# If str satisfy
# the given conditions
if (checkPalinK(str, K)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check if
// the string satisfies
// the given conditions or not
public static bool 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[256];
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
public static void Main(String []args)
{
String str = "geeksforgeeks";
int K = 2;
// If str satisfy
// the given conditions
if (checkPalinK(str, K))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check if
// the string satisfies
// the given conditions or not
function checkPalinK(str, K)
{
// Stores length of
// given string
var N = str.length;
// Stores frequency of
// each character of str
var cntFreq = Array(256).fill(0);
var i;
for (i = 0; i < N;
i++) {
// Update frequency of
// current character
cntFreq[str[i]] += 1;
}
// Stores count of
// distinct character
// whose frequency is odd
var cntOddFreq = 0;
// Traverse the cntFreq[]
// array.
for (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
var str = "geeksforgeeks";
var K = 2;
// If str satisfy
// the given conditions
if (checkPalinK(str, K)) {
document.write("Yes");
}
else {
document.write("No");
}
</script>
Producción:
Yes
Complejidad de tiempo: O (N + 256), donde N es la longitud de la string dada.
Espacio Auxiliar: O(256)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA