Dada una string S de longitud N y un entero K , la tarea es encontrar los reemplazos mínimos de caracteres necesarios para hacer que la string sea palindrómica y K-periódica .
Ejemplos:
Entrada: S = “abaaba”, K = 2
Salida: 2
Explicación: La forma óptima es transformar la string en “a a aa a a”. Por lo tanto, el número mínimo de cambios necesarios es de 2.Entrada: S = “aabbcbbcb”, K = 3
Salida: 2
Explicación:
La forma óptima es transformar la string a “ bc bbcbbcb”. Por lo tanto, el número mínimo de cambios necesarios es de 2.
Enfoque: Para minimizar el número de cambios necesarios para realizar en la string, observe la siguiente propiedad de la string transformada que es palindrómica y K-periódica:
- Una string K-periódica solo se puede formar concatenando varias strings palindrómicas que tienen una longitud K.
- Todos los caracteres en las posiciones i, K – i – 1, i + K, 2K – i – 1, i + 2K, 3K – i – 1, i + 3K, … para todo 0 ≤ i < K , son iguales .
El problema se reduce a hacer que todos los caracteres sean iguales al que aparece el máximo número de veces en estas posiciones en la string dada. Siga los pasos a continuación para resolver el problema anterior:
- Inicialice una variable ans con 0 que almacene los cambios mínimos necesarios para satisfacer la condición dada.
- Iterar sobre el rango [0, K / 2] usando la variable i.
- Crea un hashmap , mp para almacenar la frecuencia de cada carácter .
- Itere sobre los caracteres de la string a partir de i en intervalos de K usando una variable j y almacene la frecuencia de cada carácter .
- Itere la string a la inversa , comenzando desde (N – i – 1) en intervalos de K usando una variable j y almacene la frecuencia de cada carácter . Si K es impar e i = K/2 , salga del ciclo .
- Encuentre la frecuencia máxima de un carácter entre los visitados y guárdelo en una variable, digamos curr_max .
- Después de los pasos anteriores, si K es impar e i = K/2 , entonces incremente ans por (N/K – curr_max) De lo contrario, incremente ans por (N/K – 2*curr_max).
- Después de los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of changes to make the string K-
// periodic and palindrome
int findMinimumChanges(int N, int K,
string S)
{
// Initialize ans with 0
int ans = 0;
// Iterate from 0 to (K+1) / 2
for (int i = 0; i < (K + 1) / 2; i++) {
// Store frequency of character
map<char, int> mp;
// Iterate through all indices,
// i, i+K, i+2k.... and store
// the frequency of character
for (int j = i; j < N; j += K) {
// Increase the frequency
// of current character
mp[S[j]]++;
}
// Iterate through all indices
// K-i, 2K-i, 3K-i.... and store
// the frequency of character
for (int j = N - i - 1;
j >= 0; j -= K) {
// If K is odd & i is samw
// as K/2, break the loop
if (K & 1 and i == K / 2)
break;
// Increase the frequency
// of current character
mp[S[j]]++;
}
// Find the maximum frequency
// of a character among all
// visited characters
int curr_max = INT_MIN;
for (auto p : mp)
curr_max = max(curr_max,
p.second);
// If K is odd and i is same
// as K/2 then, only N/K
// characters is visited
if (K & 1 and i == K / 2)
ans += (N / K - curr_max);
// Otherwise N/K * 2 characters
// has visited
else
ans += (N / K * 2 - curr_max);
}
// Return the result
return ans;
}
// Driver Code
int main()
{
string S = "aabbcbbcb";
int N = S.length();
int K = 3;
// Function Call
cout << findMinimumChanges(N, K, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum number
// of changes to make the String K-
// periodic and palindrome
static int findMinimumChanges(int N, int K,
char[] S)
{
// Initialize ans with 0
int ans = 0;
// Iterate from 0 to (K+1) / 2
for(int i = 0; i < (K + 1) / 2; i++)
{
// Store frequency of character
HashMap<Character, Integer> mp = new HashMap<>();
// Iterate through all indices,
// i, i+K, i+2k.... and store
// the frequency of character
for(int j = i; j < N; j += K)
{
// Increase the frequency
// of current character
if (mp.containsKey(S[j]))
{
mp.put(S[j], mp.get(S[j]) + 1);
}
else
{
mp.put(S[j], 1);
}
}
// Iterate through all indices
// K-i, 2K-i, 3K-i.... and store
// the frequency of character
for(int j = N - i - 1; j >= 0; j -= K)
{
// If K is odd & i is samw
// as K/2, break the loop
if (K % 2 == 1 && i == K / 2)
break;
// Increase the frequency
// of current character
if (mp.containsKey(S[j]))
{
mp.put(S[j], mp.get(S[j]) + 1);
}
else
{
mp.put(S[j], 1);
}
}
// Find the maximum frequency
// of a character among all
// visited characters
int curr_max = Integer.MIN_VALUE;
for(Map.Entry<Character,
Integer> p : mp.entrySet())
{
curr_max = Math.max(curr_max,
p.getValue());
}
// If K is odd and i is same
// as K/2 then, only N/K
// characters is visited
if ((K % 2 == 1) && i == K / 2)
ans += (N / K - curr_max);
// Otherwise N/K * 2 characters
// has visited
else
ans += (N / K * 2 - curr_max);
}
// Return the result
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "aabbcbbcb";
int N = S.length();
int K = 3;
// Function Call
System.out.print(findMinimumChanges(
N, K, S.toCharArray()));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the
# above approach
import sys
# Function to find the minimum
# number of changes to make
# the string K- periodic and
# palindrome
def findMinimumChanges(N, K, S):
# Initialize ans with 0
ans = 0
# Iterate from 0 to (K+1) / 2
for i in range((K + 1) // 2):
# Store frequency of
# character
mp = {}
# Iterate through all indices,
# i, i+K, i+2k.... and store
# the frequency of character
for j in range(i, N, K):
# Increase the frequency
# of current character
mp[S[j]] = mp.get(S[j], 0) + 1
# Iterate through all indices
# K-i, 2K-i, 3K-i.... and store
# the frequency of character
j = N - i - 1
while(j >= 0):
# If K is odd & i is samw
# as K/2, break the loop
if ((K & 1) and
(i == K // 2)):
break
# Increase the frequency
# of current character
mp[S[j]] = mp.get(S[j], 0) + 1
j -= K
# Find the maximum frequency
# of a character among all
# visited characters
curr_max = -sys.maxsize - 1
for key, value in mp.items():
curr_max = max(curr_max,
value)
# If K is odd and i is same
# as K/2 then, only N/K
# characters is visited
if ((K & 1) and
(i == K // 2)):
ans += (N // K - curr_max)
# Otherwise N/K * 2
# characters has visited
else:
ans += (N // K * 2 -
curr_max)
# Return the result
return ans
# Driver Code
if __name__ == '__main__':
S = "aabbcbbcb"
N = len(S)
K = 3
# Function Call
print(findMinimumChanges(N, K, S))
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum number
// of changes to make the String K-
// periodic and palindrome
static int findMinimumChanges(int N, int K,
char[] S)
{
// Initialize ans with 0
int ans = 0;
// Iterate from 0 to (K+1) / 2
for(int i = 0; i < (K + 1) / 2; i++)
{
// Store frequency of character
Dictionary<char,
int> mp = new Dictionary<char,
int>();
// Iterate through all indices,
// i, i+K, i+2k.... and store
// the frequency of character
for(int j = i; j < N; j += K)
{
// Increase the frequency
// of current character
if (mp.ContainsKey(S[j]))
{
mp[S[j]]++;
}
else
{
mp.Add(S[j], 1);
}
}
// Iterate through all indices
// K-i, 2K-i, 3K-i.... and store
// the frequency of character
for(int j = N - i - 1; j >= 0; j -= K)
{
// If K is odd & i is samw
// as K/2, break the loop
if (K % 2 == 1 && i == K / 2)
break;
// Increase the frequency
// of current character
if (mp.ContainsKey(S[j]))
{
mp[S[j]]++;
}
else
{
mp.Add(S[j], 1);
}
}
// Find the maximum frequency
// of a character among all
// visited characters
int curr_max = int.MinValue;
foreach(KeyValuePair<char,
int> p in mp)
{
curr_max = Math.Max(curr_max,
p.Value);
}
// If K is odd and i is same
// as K/2 then, only N/K
// characters is visited
if ((K % 2 == 1) && i == K / 2)
ans += (N / K - curr_max);
// Otherwise N/K * 2 characters
// has visited
else
ans += (N / K * 2 - curr_max);
}
// Return the result
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String S = "aabbcbbcb";
int N = S.Length;
int K = 3;
// Function Call
Console.Write(findMinimumChanges(
N, K, S.ToCharArray()));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of changes to make the string K-
// periodic and palindrome
function findMinimumChanges(N, K, S)
{
// Initialize ans with 0
var ans = 0;
// Iterate from 0 to (K+1) / 2
for (var i = 0; i < parseInt((K + 1) / 2); i++) {
// Store frequency of character
var mp = new Map();
// Iterate through all indices,
// i, i+K, i+2k.... and store
// the frequency of character
for (var j = i; j < N; j += K) {
// Increase the frequency
// of current character
if(mp.has(S[j]))
{
mp.set(S[j], mp.get(S[j])+1);
}
else
{
mp.set(S[j], 1);
}
}
// Iterate through all indices
// K-i, 2K-i, 3K-i.... and store
// the frequency of character
for (var j = N - i - 1;
j >= 0; j -= K) {
// If K is odd & i is samw
// as K/2, break the loop
if ((K & 1) && i == parseInt(K / 2))
break;
// Increase the frequency
// of current character
if(mp.has(S[j]))
{
mp.set(S[j], mp.get(S[j])+1);
}
else
{
mp.set(S[j], 1);
}
}
// Find the maximum frequency
// of a character among all
// visited characters
var curr_max = -1000000000;
mp.forEach((value, key) => {
curr_max = Math.max(curr_max,
value);
});
// If K is odd and i is same
// as K/2 then, only N/K
// characters is visited
if (K & 1 && i == parseInt(K / 2))
ans += (parseInt(N / K) - curr_max);
// Otherwise N/K * 2 characters
// has visited
else
ans += (parseInt(N / K) * 2 - curr_max);
}
// Return the result
return ans;
}
// Driver Code
var S = "aabbcbbcb";
var N = S.length;
var K = 3;
// Function Call
document.write( findMinimumChanges(N, K, S));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vashisthamadhur2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA