Dada una string S de tamaño N y un entero positivo K (donde N % K = 0) , la tarea es encontrar el número mínimo de caracteres necesarios para ser reemplazados de modo que la string sea K -periódica y la K – longitud string periódica debe ser un palindromo .
Ejemplos:
Entrada: S = “abaaba”, K = 3
Salida: 0
Explicación: La string dada ya es K-periódica y la string periódica “aba” es palindrómica.Entrada: S = “abaaba”, K = 2
Salida: 2
Explicación: Al cambiar los caracteres en el índice 1 y 4 a ‘a’, la string actualizada “aaaaaa” es K-periódica y la string periódica “aa” es palindrómica. Por lo tanto, los cambios mínimos requeridos son 2.
Enfoque: la idea es crear un gráfico a partir de los índices de string dados y realizar DFS Traversals para encontrar la cantidad requerida de cambios. Siga los pasos a continuación para resolver este problema:
- Inicialice un total variable como 0 para almacenar el recuento de cambios necesarios.
- De acuerdo con las condiciones dadas, cree un gráfico a partir de la string y, en la string final, todos los caracteres en las posiciones i, K − i +1, K + i, 2K − i +1, 2K + i, 3K − i + 1, … para todo 1 ≤ i ≤ K debe ser igual.
- Iterar sobre el rango [0, N] y agregar un borde no dirigido entre el índice i y (N – i – 1) .
- Iterar sobre el rango [0, N – M] y agregar un borde no dirigido entre el índice i y (i + K) .
- Para minimizar el número requerido de operaciones, haga que todas las letras sean iguales a la que aparece más en estas posiciones, que se puede encontrar fácilmente realizando DFS Traversal en la string.
- Realice el DFS Traversal en el gráfico creado para todos los Nodes no visitados:
- Encuentre el elemento máximo con la frecuencia máxima entre los caracteres visitados en ese recorrido (por ejemplo, maxFrequency ).
- Actualice el número total de cambios en los caracteres por la diferencia del conteo de todos los caracteres visitados en DFS Traversal y la frecuencia máxima en el paso anterior.
- Después de completar los pasos anteriores, imprima el valor del total 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 add an edge to graph
void addEdge(vector<int> adj[], int u,
int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Function to perform DFS traversal on the
// graph recursively from a given vertex u
void DFS(int u, vector<int> adj[],
int& cnt, vector<bool>& visited,
int fre[], string S)
{
// Visit the current vertex
visited[u] = true;
// Total number of nodes
// in this component
cnt++;
// Increment the frequency of u
fre[S[u] - 'a']++;
for (int i = 0;
i < adj[u].size(); i++) {
if (!visited[adj[u][i]]) {
DFS(adj[u][i], adj, cnt,
visited, fre, S);
}
}
}
// Function for finding the minimum
// number changes required in given string
int minimumOperations(string& S, int m)
{
int V = 100;
vector<int> adj[V];
int total = 0, N = S.length();
// Form the edges according to the
// given conditions
for (int i = 0; i < N; i++) {
addEdge(adj, i, N - i - 1);
addEdge(adj, N - i - 1, i);
}
for (int i = 0; i < N - m; i++) {
addEdge(adj, i, i + m);
addEdge(adj, i + m, i);
}
// Find minimum number of operations
vector<bool> visited(V, 0);
for (int i = 0; i < N; i++) {
// Frequency array for finding
// the most frequent character
if (!visited[i]) {
// Frequency array for finding
// the most frequent character
int fre[26] = { 0 };
int cnt = 0, maxx = -1;
DFS(i, adj, cnt, visited, fre, S);
// Finding most frequent character
for (int j = 0; j < 26; j++)
maxx = max(maxx, fre[j]);
// Change rest of the characters
// to most frequent one
total += cnt - maxx;
}
}
// Print total number of changes
cout << total;
}
// Driver Code
int main()
{
string S = "abaaba";
int K = 2;
// Function Call
minimumOperations(S, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to add an edge to graph
static void addEdge(Vector<Integer> adj[], int u,
int v)
{
adj[u].add(v);
adj[v].add(u);
}
static int cnt = 0;
static boolean[] visited;
// Function to perform DFS traversal on the
// graph recursively from a given vertex u
static void DFS(int u, Vector<Integer> adj[],
int fre[], String S)
{
// Visit the current vertex
visited[u] = true;
// Total number of nodes
// in this component
cnt++;
// Increment the frequency of u
fre[S.charAt(u) - 'a']++;
for(int i = 0; i < adj[u].size(); i++)
{
if (!visited[adj[u].get(i)])
{
DFS(adj[u].get(i), adj, fre, S);
}
}
}
// Function for finding the minimum
// number changes required in given String
static void minimumOperations(String S, int m)
{
int V = 100;
@SuppressWarnings("unchecked")
Vector<Integer> []adj = new Vector[V];
int total = 0, N = S.length();
for(int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
// Form the edges according to the
// given conditions
for(int i = 0; i < N; i++)
{
addEdge(adj, i, N - i - 1);
addEdge(adj, N - i - 1, i);
}
for(int i = 0; i < N - m; i++)
{
addEdge(adj, i, i + m);
addEdge(adj, i + m, i);
}
// Find minimum number of operations
visited = new boolean[V];
for(int i = 0; i < N; i++)
{
// Frequency array for finding
// the most frequent character
if (!visited[i])
{
// Frequency array for finding
// the most frequent character
int fre[] = new int[26];
cnt = 0;
int maxx = -1;
DFS(i, adj, fre, S);
// Finding most frequent character
for(int j = 0; j < 26; j++)
maxx = Math.max(maxx, fre[j]);
// Change rest of the characters
// to most frequent one
total += cnt - maxx;
}
}
// Print total number of changes
System.out.print(total);
}
// Driver Code
public static void main(String[] args)
{
String S = "abaaba";
int K = 2;
// Function Call
minimumOperations(S, K);
}
}
// This code is contributed by aashish1995
Python3
# Python3 program for the above approach
import sys
sys.setrecursionlimit(1500)
# Function to add an edge to graph
def addEdge(u, v):
global adj
adj[u].append(v)
adj[v].append(u)
# Function to perform DFS traversal on the
# graph recursively from a given vertex u
def DFS(u, fre, S):
global visited, adj, cnt
# Visit the current vertex
visited[u] = 1
# Total number of nodes
# in this component
cnt += 1
# Increment the frequency of u
fre[ord(S[u]) - ord('a')] += 1
for i in adj[u]:
if (visited[i] == 0):
DFS(i, fre, S)
# Function for finding the minimum
# number changes required in given string
def minimumOperations(S, m):
global adj, visited, cnt
total, N = 0, len(S)
# Form the edges according to the
# given conditions
for i in range(N):
addEdge(i, N - i - 1)
addEdge(N - i - 1, i)
for i in range(N-m):
addEdge(i, i + m)
addEdge(i + m, i)
for i in range(N):
# Frequency array for finding
# the most frequent character
if (not visited[i]):
# Frequency array for finding
# the most frequent character
fre = [0] * 26
cnt, maxx = 0, -1
DFS(i, fre, S)
# Finding most frequent character
for j in range(26):
maxx = max(maxx, fre[j])
# Change rest of the characters
# to most frequent one
total += cnt - maxx
# Print total number of changes
print (total)
# Driver Code
if __name__ == '__main__':
adj = [[] for i in range(101)]
visited, cnt = [0 for i in range(101)], 0
S = "abaaba"
K = 2
# Function Call
minimumOperations(S, K)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to add an edge to graph
static void addEdge(List<int> []adj, int u,
int v)
{
adj[u].Add(v);
adj[v].Add(u);
}
static int cnt = 0;
static bool[] visited;
// Function to perform DFS traversal on the
// graph recursively from a given vertex u
static void DFS(int u, List<int> []adj,
int []fre, String S)
{
// Visit the current vertex
visited[u] = true;
// Total number of nodes
// in this component
cnt++;
// Increment the frequency of u
fre[S[u] - 'a']++;
for(int i = 0; i < adj[u].Count; i++)
{
if (!visited[adj[u][i]])
{
DFS(adj[u][i], adj, fre, S);
}
}
}
// Function for finding the minimum
// number changes required in given String
static void minimumOperations(String S, int m)
{
int V = 100;
List<int> []adj = new List<int>[V];
int total = 0, N = S.Length;
for(int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
// Form the edges according to the
// given conditions
for(int i = 0; i < N; i++)
{
addEdge(adj, i, N - i - 1);
addEdge(adj, N - i - 1, i);
}
for(int i = 0; i < N - m; i++)
{
addEdge(adj, i, i + m);
addEdge(adj, i + m, i);
}
// Find minimum number of operations
visited = new bool[V];
for(int i = 0; i < N; i++)
{
// Frequency array for finding
// the most frequent character
if (!visited[i])
{
// Frequency array for finding
// the most frequent character
int []fre = new int[26];
cnt = 0;
int maxx = -1;
DFS(i, adj, fre, S);
// Finding most frequent character
for(int j = 0; j < 26; j++)
maxx = Math.Max(maxx, fre[j]);
// Change rest of the characters
// to most frequent one
total += cnt - maxx;
}
}
// Print total number of changes
Console.Write(total);
}
// Driver Code
public static void Main(String[] args)
{
String S = "abaaba";
int K = 2;
// Function Call
minimumOperations(S, K);
}
}
// This code is contributed by aashish1995
Javascript
<script>
// Javascript program for the above approach
// Function to add an edge to graph
function addEdge(adj, u, v)
{
adj[u].push(v);
adj[v].push(u);
}
let cnt = 0;
let visited;
// Function to perform DFS traversal on the
// graph recursively from a given vertex u
function DFS(u, adj, fre, S)
{
// Visit the current vertex
visited[u] = true;
// Total number of nodes
// in this component
cnt++;
// Increment the frequency of u
fre[S[u].charCodeAt() - 'a'.charCodeAt()]++;
for(let i = 0; i < adj[u].length; i++)
{
if (!visited[adj[u][i]])
{
DFS(adj[u][i], adj, fre, S);
}
}
}
// Function for finding the minimum
// number changes required in given String
function minimumOperations(S, m)
{
let V = 100;
let adj = [];
for(let i = 0; i < V; i++)
{
adj.push([]);
}
let total = 0, N = S.length;
for(let i = 0; i < adj.length; i++)
adj[i] = [];
// Form the edges according to the
// given conditions
for(let i = 0; i < N; i++)
{
addEdge(adj, i, N - i - 1);
addEdge(adj, N - i - 1, i);
}
for(let i = 0; i < N - m; i++)
{
addEdge(adj, i, i + m);
addEdge(adj, i + m, i);
}
// Find minimum number of operations
visited = new Array(V);
visited.fill(false);
for(let i = 0; i < N; i++)
{
// Frequency array for finding
// the most frequent character
if (!visited[i])
{
// Frequency array for finding
// the most frequent character
let fre = new Array(26);
fre.fill(0);
cnt = 0;
let maxx = -1;
DFS(i, adj, fre, S);
// Finding most frequent character
for(let j = 0; j < 26; j++)
maxx = Math.max(maxx, fre[j]);
// Change rest of the characters
// to most frequent one
total += cnt - maxx;
}
}
// Print total number of changes
document.write(total);
}
// Driver code
let S = "abaaba";
let K = 2;
// Function Call
minimumOperations(S, K);
// This code is contributed by decode2207.
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por reapedjuggler y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA