Dada una string ternaria S de longitud N que contiene solo los caracteres ‘0’ , ‘1’ y ‘2’ y consultas Q que contienen un rango de índices [L, R] , la tarea para cada consulta [L, R] es encontrar el número mínimo de caracteres para convertir a ‘0’ , ‘1’ o ‘2’ de modo que no exista una substring palindrómica de al menos 2 de longitud, entre str[L] y str[R] .
Ejemplos:
Entrada: N = 10, Q = 3, S = “0200011011”, consultas = {0, 4}, {1, 6}, {2, 8} Salida: 2 3 3 Explicación: Consulta 1: {
0 ,
4
} ⇒ s = “02000” las substrings palindrómicas presentes son “020”, “00”, “000”. Las substrings se pueden cambiar a «02 1 0 2 » con 2 cambios. “acbac” tiene cero substrings palindrómicas.
Consulta 2: {1, 6} ⇒ s = “200011” las substrings palindrómicas presentes son “00”, “000”, “11”. La substring s se puede cambiar a «20 120 1″ con 3 cambios. “cabcab” tiene cero substrings palindrómicas.
Consulta 3: {2, 8} ⇒ s = “aaabbab” las substrings palindrómicas presentes son “00″, “000”, “0110”, “11”, “101”. La substring s se puede cambiar a “ 12 01 201″ con 3 cambios. “1201201” tiene cero substrings palindrómicas.Entrada: N = 5, Q = 2, S = “bccab”, consultas = {0, 4}, {1, 2}
Salida: 2 1
Enfoque ingenuo: el problema dado se puede resolver modificando recursivamente cada carácter de la substring para una consulta determinada y verificando si la substring resultante tiene substrings palindrómicas .
Complejidad temporal: O(Q*3 N )
Espacio auxiliar: O(N)
Enfoque Eficiente: El problema dado puede ser resuelto usando Programación Dinámica , la idea es preprocesar las posibles respuestas para todas las substrings usando las siguientes observaciones:
- Una string tiene cero substrings palindrómicas si s i ≠ s i-1 y s i ≠ s i-2 , es decir, no hay dos caracteres adyacentes iguales ni dos caracteres alternativos iguales por las siguientes razones:
- Se forman palíndromos de longitud uniforme si los caracteres adyacentes son iguales.
- Se forman palíndromos de longitud impar si los caracteres alternativos son iguales.
- Si el primer carácter de la string es ‘0’, entonces el siguiente carácter debe ser ‘1’ o ‘2’ (ya que s i ≠ s i-1 )
- Si el segundo carácter es ‘1’, entonces el tercer carácter no puede ser ‘0’ (ya que s i ≠ s i-2 ) o ‘1’ (ya que s i ≠ s i-1 )
- Por lo tanto, el tercer carácter será ‘2’. Entonces el cuarto carácter solo puede ser ‘1’. La string formada es “012012012..”
- De manera similar, después de permutar los caracteres ‘0’, ‘1’ y ‘2’ y repetir cada permutación varias veces, obtenemos las strings de destino «012012012…», «120120120…», «021021021…», etc.
- Hay seis permutaciones posibles con los caracteres ‘0’, ‘1’ y ‘2’ y, por lo tanto, seis strings de destino
Ahora, cada consulta se puede resolver transformando la substring del carácter L a R en las seis strings de destino y verificando cuál de ellas requiere menos operaciones. Este enfoque requiere tiempo O(N) para cada consulta. El enfoque se puede optimizar aún más preprocesando la string dada. La siguiente es la solución optimizada:
- Sea prefix[i] la array que contiene el número mínimo de operaciones necesarias para transformar la string en la string de destino i . Por lo tanto, prefix[i][j] es el número de operaciones necesarias para transformar los primeros j caracteres de la string en la string de destino i .
- Después del preprocesamiento del paso anterior, cada consulta j se puede resolver en O(1) tiempo usando la fórmula para cada posible string preprocesada como el mínimo de currentCost y (prefix[i][r j ] – prefix[i][l j – 1]) para todas las secuencias posibles e imprimir el costo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define SIZE 100005
using namespace std;
// Function to preprocess the cost of
// converting the first j character to
// each sequence prefix[i]
void preprocess(string& s, string& t,
int prefix[][SIZE],
int n, int i)
{
// Initialize DP array
prefix[i][0] = (s[0] != t[0]);
for (int j = 1; j < n; j++) {
// prefix[i][j] defines minimum
// operations to transform first j
// characters of s into sequence i
prefix[i][j]
= prefix[i][j - 1]
+ (s[j] != t[j % 3]);
}
return;
}
// Function to find the minimum number of
// changes required to make each substring
// between [L, R] non-palindromic
void minChangesNonPalindrome(
string str, int N, int Q,
vector<pair<int, int> > queries)
{
// Initialize the DP array
int prefix[6][SIZE];
// Initialize the 6 different patterns
// that can be formed to make substrings
// non palindromic
vector<string> sequences
= { "012", "021", "102",
"120", "201", "210" };
for (int i = 0; i < 6; i++) {
// Preprocess the string with
// the ith sequence
preprocess(str, sequences[i],
prefix, N, i);
}
// Iterate through queries
for (int i = 0; i < Q; i++) {
int l = queries[i].first + 1,
r = queries[i].second + 1;
int cost = INT_MAX;
// Find the minimum operations by
// comparing 6 different patterns
// of the substrings
for (int j = 0; j < 6; j++) {
// Find the cost
cost
= min(
cost,
prefix[j][r]
- prefix[j][l]
+ (str[l] != sequences[j][l % 3]));
}
cout << cost << '\n';
}
}
// Driver Code
int main()
{
string S = "0200011011";
vector<pair<int, int> > queries
= { { 0, 4 }, { 1, 6 }, { 2, 8 } };
int N = S.length();
int Q = queries.size();
minChangesNonPalindrome(
S, N, Q, queries);
return 0;
}
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
public static int SIZE = 100005;
// Function to preprocess the cost of
// converting the first j character to
// each sequence prefix[i]
public static void preprocess(String s, String t, int prefix[][], int n, int i)
{
// Initialize DP array
prefix[i][0] = ((s.charAt(0) != t.charAt(0)) ? 1 : 0);
for (int j = 1; j < n; j++) {
// prefix[i][j] defines minimum
// operations to transform first j
// characters of s into sequence i
prefix[i][j] = prefix[i][j - 1] + (s.charAt(j) != t.charAt(j%3) ? 1 : 0);
}
}
// Function to find the minimum number of
// changes required to make each substring
// between [L, R] non-palindromic
public static void minChangesNonPalindrome(String str, int N, int Q, ArrayList<ArrayList<Integer>> queries)
{
// Initialize the DP array
int prefix[][] = new int[6][SIZE];
// Initialize the 6 different patterns
// that can be formed to make substrings
// non palindromic
ArrayList<String> sequences = new ArrayList<String>(
List.of(
"012",
"021",
"102",
"120",
"201",
"210"
)
);
for (int i = 0; i < 6; i++) {
// Preprocess the string with
// the ith sequence
preprocess(str, sequences.get(i), prefix, N, i);
}
// Iterate through queries
for (int i = 0 ; i < Q ; i++) {
int l = queries.get(i).get(0) + 1,
r = queries.get(i).get(1) + 1;
int cost = Integer.MAX_VALUE;
// Find the minimum operations by
// comparing 6 different patterns
// of the substrings
for (int j = 0 ; j < 6 ; j++) {
// Find the cost
cost = Math.min(cost, prefix[j][r] - prefix[j][l] + (str.charAt(l) != sequences.get(j).charAt(l % 3) ? 1 : 0));
}
System.out.println(cost);
}
}
// Driver code
public static void main(String args[])
{
String S = "0200011011";
ArrayList<ArrayList<Integer>> queries = new ArrayList<ArrayList<Integer>>(
List.of(
new ArrayList<Integer>(
List.of(0, 4)
),
new ArrayList<Integer>(
List.of(1, 6)
),
new ArrayList<Integer>(
List.of(2, 8)
)
)
);
int N = S.length();
int Q = queries.size();
minChangesNonPalindrome(S, N, Q, queries);
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python 3 program for the above approach import sys SIZE = 100005 # Function to preprocess the cost of # converting the first j character to # each sequence prefix[i] def preprocess(s, t, prefix, n, i): # Initialize DP array prefix[i][0] = (s[0] != t[0]) for j in range(1, n): # prefix[i][j] defines minimum # operations to transform first j # characters of s into sequence i prefix[i][j] = prefix[i][j - 1] + (s[j] != t[j % 3]) return # Function to find the minimum number of # changes required to make each substring # between [L, R] non-palindromic def minChangesNonPalindrome( st, N, Q, queries): # Initialize the DP array prefix = [[0 for x in range(SIZE)]for y in range(6)] # Initialize the 6 different patterns # that can be formed to make substrings # non palindromic sequences = ["012", "021", "102", "120", "201", "210"] for i in range(6): # Preprocess the string with # the ith sequence preprocess(st, sequences[i], prefix, N, i) # Iterate through queries for i in range(Q): l = queries[i][0] + 1 r = queries[i][1] + 1 cost = sys.maxsize-1 # Find the minimum operations by # comparing 6 different patterns # of the substrings for j in range(6): # Find the cost cost = min(cost, prefix[j][r] - prefix[j][l] + (st[l] != sequences[j][l % 3])) print(cost) # Driver Code if __name__ == "__main__": S = "0200011011" queries = [[0, 4], [1, 6], [2, 8]] N = len(S) Q = len(queries) minChangesNonPalindrome( S, N, Q, queries) # This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
let SIZE = 100005
// Function to preprocess the cost of
// converting the first j character to
// each sequence prefix[i]
function preprocess(s, t,
prefix, n, i)
{
// Initialize DP array
prefix[i][0] = (s[0] != t[0]);
for (let j = 1; j < n; j++) {
// prefix[i][j] defines minimum
// operations to transform first j
// characters of s into sequence i
prefix[i][j]
= prefix[i][j - 1]
+ (s[j] != t[j % 3]);
}
return prefix;
}
// Function to find the minimum number of
// changes required to make each substring
// between [L, R] non-palindromic
function minChangesNonPalindrome(
str, N, Q, queries)
{
// Initialize the DP array
let prefix = new Array(6);
for (let i = 0; i < prefix.length; i++)
prefix[i] = new Array(SIZE).fill(0);
// Initialize the 6 different patterns
// that can be formed to make substrings
// non palindromic
let sequences
= ["012", "021", "102",
"120", "201", "210"];
for (let i = 0; i < 6; i++) {
// Preprocess the string with
// the ith sequence
prefix = preprocess(str, sequences[i],
prefix, N, i);
}
// Iterate through queries
for (let i = 0; i < Q; i++) {
let l = queries[i].first + 1,
r = queries[i].second + 1;
let cost = Number.MAX_VALUE;
// Find the minimum operations by
// comparing 6 different patterns
// of the substrings
for (let j = 0; j < 6; j++) {
// Find the cost
cost
= Math.min(
cost,
prefix[j][r]
- prefix[j][l]
+ (str[l] != sequences[j][l % 3]));
}
document.write(cost + '<br>');
}
}
// Driver Code
let S = "0200011011";
let queries
= [{ first: 0, second: 4 }, { first: 1, second: 6 }, { first: 2, second: 8 }];
let N = S.length;
let Q = queries.length;
minChangesNonPalindrome(
S, N, Q, queries);
// This code is contributed by Potta Lokesh
</script>
Producción:
2 3 3
Complejidad temporal: O(N + Q)
Espacio auxiliar: O(N)