Dada una string str y Q consultas en forma de [L, R, K] , la tarea es encontrar si los caracteres de la string de [L, R] con un máximo de K cambios permitidos se pueden reorganizar para hacer que la string sea palindrómica o no . . Para cada consulta, imprima «SÍ» si puede convertirse en una string palindrómica; de lo contrario, imprima «NO» .
Ejemplos:
Entrada: str = «GeeksforGeeks», Q = { { 1, 5, 3 }, { 5, 7, 0 }, { 8, 11, 3 }, {3, 10, 5 }, { 0, 9, 5 } }
Salida:
SÍ
NO
SÍ
SÍ
SÍ
Explicación:
consultas[0]: substring = “eeksf”, podría cambiarse a “eekee”, que es palíndromo.
consultas[1]: substring = “para”, no es palíndromo y no se puede convertir en palíndromo después de reemplazar como máximo 0 caracteres.
consultas[2]: substring = “Caramba”, podría cambiarse a “GeG”, que es palíndromo.
consultas[3]: substring = “ksforGee”, podría cambiarse a “ksfoofsk”, que es un palíndromo.
consultas[4]: substring = «GeeksforGe», podría cambiarse a «GeeksskeeG», que es palíndromo.
Aporte:str = “abczwerte”, Q = { { 3, 7, 4 }, { 1, 8, 10 }, { 0, 3, 1 } }
Salida:
SÍ
SÍ
NO
Enfoque: Este problema se puede resolver usando Programación Dinámica .
- Cree una array 2D (digamos dp[i][j] ) donde dp[i][j] denota el conteo del i-ésimo carácter en la substring str[0…j] .
- A continuación se muestra la relación de recurrencia para el enfoque anterior:
- Si str[i] es igual a str[j], entonces dp[i][j] = 1 + dp[i][j-1] .
- Si str[i] no es igual a str[j], entonces dp[i][j] = dp[i][j-1] .
- si j es igual a 0, entonces dp[i][j] sería uno de los primeros caracteres que son iguales a i-ésimos caracteres.
- Para cada consulta, averigüe el recuento de cada carácter en la substring str[L…R] mediante la relación simple:
count = dp[i][right] - dp[i][left] + (str[left] == i + 'a').
- Obtenga el recuento de pares no coincidentes.
- Ahora necesitamos convertir la mitad de los caracteres no coincidentes en los caracteres restantes. Si el recuento de la mitad de los caracteres no coincidentes es menor o igual a K , imprima «SÍ», de lo contrario, imprima «NO» .
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 whether string can
// be made palindromic or not for each queries
void canMakePaliQueries(
string str,
vector<vector<int> >& Q)
{
int n = str.length();
// To store the count of ith character
// of substring str[0...i]
vector<vector<int> > dp(
26,
vector<int>(n, 0));
for (int i = 0; i < 26; i++) {
// Current character
char currentChar = i + 'a';
for (int j = 0; j < n; j++) {
// Update dp[][] on the basis
// recurrence relation
if (j == 0) {
dp[i][j]
= (str[j] == currentChar);
}
else {
dp[i][j]
= dp[i][j - 1]
+ (str[j] == currentChar);
}
}
}
// For each queries
for (auto query : Q) {
int left = query[0];
int right = query[1];
int k = query[2];
// To store the count of
// distinct character
int unMatchedCount = 0;
for (int i = 0; i < 26; i++) {
// Find occurrence of i + 'a'
int occurrence
= dp[i][right]
- dp[i][left]
+ (str[left] == (i + 'a'));
if (occurrence & 1)
unMatchedCount++;
}
// Half the distinct Count
int ans = unMatchedCount / 2;
// If half the distinct count is
// less than equals to K then
// palindromic string can be made
if (ans <= k) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
}
// Driver Code
int main()
{
// Given string str
string str = "GeeksforGeeks";
// Given Queries
vector<vector<int> > Q;
Q = { { 1, 5, 3 }, { 5, 7, 0 },
{ 8, 11, 3 }, { 3, 10, 5 },
{ 0, 9, 5 } };
// Function call
canMakePaliQueries(str, Q);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find whether String can be
// made palindromic or not for each queries
static void canMakePaliQueries(String str,
int [][]Q)
{
int n = str.length();
// To store the count of ith character
// of subString str[0...i]
int [][]dp = new int[26][n];
for(int i = 0; i < 26; i++)
{
// Current character
char currentChar = (char)(i + 'a');
for(int j = 0; j < n; j++)
{
// Update dp[][] on the basis
// recurrence relation
if (j == 0)
{
dp[i][j] = (str.charAt(j) ==
currentChar) ? 1 : 0;
}
else
{
dp[i][j] = dp[i][j - 1] +
((str.charAt(j) ==
currentChar) ? 1 : 0);
}
}
}
// For each queries
for(int []query : Q)
{
int left = query[0];
int right = query[1];
int k = query[2];
// To store the count of
// distinct character
int unMatchedCount = 0;
for(int i = 0; i < 26; i++)
{
// Find occurrence of i + 'a'
int occurrence = dp[i][right] -
dp[i][left] +
(str.charAt(left) ==
(i + 'a') ? 1 : 0);
if (occurrence % 2 == 1)
unMatchedCount++;
}
// Half the distinct Count
int ans = unMatchedCount / 2;
// If half the distinct count is
// less than equals to K then
// palindromic String can be made
if (ans <= k)
{
System.out.print("YES\n");
}
else
{
System.out.print("NO\n");
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given a String str
String str = "GeeksforGeeks";
// Given Queries
int [][]Q = { { 1, 5, 3 },
{ 5, 7, 0 },
{ 8, 11, 3 },
{ 3, 10, 5 },
{ 0, 9, 5 } };
// Function call
canMakePaliQueries(str, Q);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for
# the above approach
# Function to find whether
# string can be made palindromic
# or not for each queries
def canMakePaliQueries(str, Q):
n = len(str)
# To store the count of
# ith character of substring
# str[0...i]
dp = [[0 for i in range(n)]
for j in range(26)]\
for i in range(26):
# Current character
currentChar = chr(i + ord('a'))
for j in range(n):
# Update dp[][] on the basis
# recurrence relation
if(j == 0):
dp[i][j] = (str[j] ==
currentChar)
else:
dp[i][j] = dp[i][j - 1] +
(str[j] == currentChar)
# For each queries
for query in Q:
left = query[0]
right = query[1]
k = query[2]
# To store the count of
# distinct character
unMatchedCount = 0
for i in range(26):
# Find occurrence of
# i + 'a'
occurrence = dp[i][right] -
dp[i][left] +
(str[left] ==
chr(i + ord('a')))
if(occurrence & 1):
unMatchedCount += 1
# Half the distinct Count
ans = int(unMatchedCount / 2)
# If half the distinct count is
# less than equals to K then
# palindromic string can be made
if(ans <= k):
print("YES")
else:
print("NO")
# Driver Code
# Given string str
str = "GeeksforGeeks"
# Given Queries
Q = [[1, 5, 3],
[5, 7, 0],
[8, 11, 3],
[3, 10, 5],
[0, 9, 5]]
# Function call
canMakePaliQueries(str, Q)
# This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
class GFG{
// Function to find whether String can be
// made palindromic or not for each queries
static void canMakePaliQueries(String str,
int [,]Q)
{
int n = str.Length;
// To store the count of ith character
// of subString str[0...i]
int [,]dp = new int[26, n];
for(int i = 0; i < 26; i++)
{
// Current character
char currentChar = (char)(i + 'a');
for(int j = 0; j < n; j++)
{
// Update [,]dp on the basis
// recurrence relation
if (j == 0)
{
dp[i,j] = (str[j] ==
currentChar) ? 1 : 0;
}
else
{
dp[i,j] = dp[i, j - 1] +
((str[j] ==
currentChar) ? 1 : 0);
}
}
}
// For each queries
for(int l = 0; l < Q.GetLength(0);l++)
{
int []query = GetRow(Q,l);
int left = query[0];
int right = query[1];
int k = query[2];
// To store the count of
// distinct character
int unMatchedCount = 0;
for(int i = 0; i < 26; i++)
{
// Find occurrence of i + 'a'
int occurrence = dp[i, right] -
dp[i, left] +
(str[left] ==
(i + 'a') ? 1 : 0);
if (occurrence % 2 == 1)
unMatchedCount++;
}
// Half the distinct Count
int ans = unMatchedCount / 2;
// If half the distinct count is
// less than equals to K then
// palindromic String can be made
if (ans <= k)
{
Console.Write("YES\n");
}
else
{
Console.Write("NO\n");
}
}
}
public static int[] GetRow(int[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver Code
public static void Main(String[] args)
{
// Given a String str
String str = "GeeksforGeeks";
// Given Queries
int [,]Q = { { 1, 5, 3 },
{ 5, 7, 0 },
{ 8, 11, 3 },
{ 3, 10, 5 },
{ 0, 9, 5 } };
// Function call
canMakePaliQueries(str, Q);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program for the above approach
// Function to find whether String can be
// made palindromic or not for each queries
function canMakePaliQueries(str,Q)
{
let n = str.length;
// To store the count of ith character
// of subString str[0...i]
let dp = new Array(26);
for(let i=0;i<26;i++)
{
dp[i]=new Array(n);
for(let j=0;j<n;j++)
dp[i][j]=0;
}
for(let i = 0; i < 26; i++)
{
// Current character
let currentChar = String.fromCharCode(i + 'a'.charCodeAt(0));
for(let j = 0; j < n; j++)
{
// Update dp[][] on the basis
// recurrence relation
if (j == 0)
{
dp[i][j] = (str[j] ==
currentChar) ? 1 : 0;
}
else
{
dp[i][j] = dp[i][j - 1] +
((str[j] ==
currentChar) ? 1 : 0);
}
}
}
// For each queries
for(let query of Q.values())
{
let left = query[0];
let right = query[1];
let k = query[2];
// To store the count of
// distinct character
let unMatchedCount = 0;
for(let i = 0; i < 26; i++)
{
// Find occurrence of i + 'a'
let occurrence = dp[i][right] -
dp[i][left] +
(str[left] ==
(i + 'a'.charCodeAt(0)) ? 1 : 0);
if (occurrence % 2 == 1)
unMatchedCount++;
}
// Half the distinct Count
let ans = unMatchedCount / 2;
// If half the distinct count is
// less than equals to K then
// palindromic String can be made
if (ans <= k)
{
document.write("YES<br>");
}
else
{
document.write("NO<br>");
}
}
}
// Driver Code
// Given a String str
let str = "GeeksforGeeks";
// Given Queries
let Q=[[ 1, 5, 3 ],
[ 5, 7, 0 ],
[ 8, 11, 3 ],
[ 3, 10, 5 ],
[ 0, 9, 5 ]];
// Function call
canMakePaliQueries(str, Q);
// This code is contributed by unknown2108
</script>
Producción:
YES NO YES YES YES
Complejidad de tiempo: O(26*N), donde N es la longitud de la string.
Espacio auxiliar: O(26*N), donde N es la longitud de la string.