Reemplazos mínimos requeridos para obtener una string palindrómica periódica K

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: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *