Dada una string str y consultas Q. Cada consulta consta de dos números L y R . La tarea es encontrar el palíndromo de longitud máxima que se puede crear con caracteres en el rango [L, R] .
Ejemplos:
Entrada: str = “amim”, Q[] = {{1, 4}, {3, 4}
Salida:
3
1
En el rango [1, 4], solo se pueden formar dos palíndromos “mam” y “mim”.
En el rango [3, 4], solo se puede crear «i» o «m» usando los caracteres en el rango.
Entrada: str = “aaaa”, Q[] = {{1, 5}, {5, 5}
Salida:
5
1
Enfoque: Sea prefix[i][j] una array que denota la frecuencia del carácter char(j+97) en el rango de 1 a i. Para cualquier rango L a R, cuente las frecuencias pares y las frecuencias impares. Dado que impar-1 es par, también puede contribuir a la string palindrómica. También mantenga una marca para un carácter de frecuencia impar, que se puede insertar en el medio. Por lo tanto, la longitud del palíndromo más largo posible será la suma de todas las frecuencias pares y la suma de las frecuencias impares 1, sumando 1 si existe un carácter de frecuencia impar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 4
// Function to return the length of the
// longest palindrome that can be formed
// using the characters in the range [l, r]
int performQueries(int l, int r, int prefix[N][26])
{
// 0-based indexing
l--;
r--;
// Marks if there is an
// odd frequency character
bool flag = false;
// Length of the longest palindrome
// possible from characters in range
int count = 0;
// Traverse for all characters
// and count their frequencies
for (int i = 0; i < 26; i++) {
// Find the frequency in range 1 - r
int cnt = prefix[r][i];
// Exclude the frequencies in range 1 - (l - 1)
if (l > 0)
cnt -= prefix[l - 1][i];
// If frequency is odd, then add 1 less than
// the original frequency to make it even
if (cnt % 2 == 1) {
flag = true;
count += cnt - 1;
}
// Else completely add if even
else
count += cnt;
}
// If any odd frequency character
// is present then add 1
if (flag)
count += 1;
return count;
}
// Function to pre-calculate the frequencies
// of the characters to reduce complexity
void preCalculate(string s, int prefix[N][26])
{
int n = s.size();
// Iterate and increase the count
for (int i = 0; i < n; i++) {
prefix[i][s[i] - 'a']++;
}
// Create a prefix type array
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++)
prefix[i][j] += prefix[i - 1][j];
}
}
// Driver code
int main()
{
string s = "amim";
// Pre-calculate prefix array
int prefix[N][26];
memset(prefix, 0, sizeof prefix);
preCalculate(s, prefix);
int queries[][2] = { { 1, 4 }, { 3, 4 } };
int q = sizeof(queries) / sizeof(queries[0]);
// Perform queries
for (int i = 0; i < q; i++) {
cout << performQueries(queries[i][0],
queries[i][1], prefix)
<< endl;
}
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int N = 4 ;
// Function to return the length of the
// longest palindrome that can be formed
// using the characters in the range [l, r]
static int performQueries(int l, int r, int prefix[][])
{
// 0-based indexing
l--;
r--;
// Marks if there is an
// odd frequency character
boolean flag = false;
// Length of the longest palindrome
// possible from characters in range
int count = 0;
// Traverse for all characters
// and count their frequencies
for (int i = 0; i < 26; i++)
{
// Find the frequency in range 1 - r
int cnt = prefix[r][i];
// Exclude the frequencies in range 1 - (l - 1)
if (l > 0)
cnt -= prefix[l - 1][i];
// If frequency is odd, then add 1 less than
// the original frequency to make it even
if (cnt % 2 == 1)
{
flag = true;
count += cnt - 1;
}
// Else completely add if even
else
count += cnt;
}
// If any odd frequency character
// is present then add 1
if (flag)
count += 1;
return count;
}
// Function to pre-calculate the frequencies
// of the characters to reduce complexity
static void preCalculate(String s, int prefix[][])
{
int n = s.length();
// Iterate and increase the count
for (int i = 0; i < n; i++)
{
prefix[i][s.charAt(i) - 'a']++;
}
// Create a prefix type array
for (int i = 1; i < n; i++)
{
for (int j = 0; j < 26; j++)
prefix[i][j] += prefix[i - 1][j];
}
}
// Driver code
public static void main(String args[])
{
String s = "amim";
// Pre-calculate prefix array
int prefix[][] = new int[N][26];
preCalculate(s, prefix);
int queries[][] = { { 1, 4 }, { 3, 4 } };
int q = queries.length;
// Perform queries
for (int i = 0; i < q; i++)
{
System.out.println( performQueries(queries[i][0],
queries[i][1], prefix) );
}
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach
N = 4
# Function to return the length of the
# longest palindrome that can be formed
# using the characters in the range [l, r]
def performQueries(l, r, prefix):
# 0-based indexing
l -= 1
r -= 1
# Marks if there is an
# odd frequency character
flag = False
# Length of the longest palindrome
# possible from characters in range
count = 0
# Traverse for all characters
# and count their frequencies
for i in range(26):
# Find the frequency in range 1 - r
cnt = prefix[r][i]
# Exclude the frequencies in range 1 - (l - 1)
if (l > 0):
cnt -= prefix[l - 1][i]
# If frequency is odd, then add 1 less than
# the original frequency to make it even
if (cnt % 2 == 1):
flag = True
count += cnt - 1
# Else completely add if even
else:
count += cnt
# If any odd frequency character
# is present then add 1
if (flag):
count += 1
return count
# Function to pre-calculate the frequencies
# of the characters to reduce complexity
def preCalculate(s, prefix):
n = len(s)
# Iterate and increase the count
for i in range(n):
prefix[i][ord(s[i]) - ord('a')] += 1
# Create a prefix type array
for i in range(1, n):
for j in range(26):
prefix[i][j] += prefix[i - 1][j]
# Driver code
s = "amim"
# Pre-calculate prefix array
prefix = [[0 for i in range(26)]
for i in range(N)]
preCalculate(s, prefix)
queries = [[1, 4] , [3, 4]]
q = len(queries)
# Perform queries
for i in range(q):
print(performQueries(queries[i][0],
queries[i][1],
prefix))
# This code is contributed
# by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int N = 4 ;
// Function to return the length of the
// longest palindrome that can be formed
// using the characters in the range [l, r]
static int performQueries(int l, int r, int[,] prefix)
{
// 0-based indexing
l--;
r--;
// Marks if there is an
// odd frequency character
bool flag = false;
// Length of the longest palindrome
// possible from characters in range
int count = 0;
// Traverse for all characters
// and count their frequencies
for (int i = 0; i < 26; i++)
{
// Find the frequency in range 1 - r
int cnt = prefix[r, i];
// Exclude the frequencies in range 1 - (l - 1)
if (l > 0)
cnt -= prefix[l - 1, i];
// If frequency is odd, then add 1 less than
// the original frequency to make it even
if (cnt % 2 == 1)
{
flag = true;
count += cnt - 1;
}
// Else completely add if even
else
count += cnt;
}
// If any odd frequency character
// is present then add 1
if (flag)
count += 1;
return count;
}
// Function to pre-calculate the frequencies
// of the characters to reduce complexity
static void preCalculate(string s, int[,] prefix)
{
int n = s.Length;
// Iterate and increase the count
for (int i = 0; i < n; i++)
{
prefix[i, s[i] - 'a']++;
}
// Create a prefix type array
for (int i = 1; i < n; i++)
{
for (int j = 0; j < 26; j++)
prefix[i, j] += prefix[i - 1, j];
}
}
// Driver code
public static void Main()
{
string s = "amim";
// Pre-calculate prefix array
int[,] prefix = new int[N, 26];
preCalculate(s, prefix);
int[,] queries = { { 1, 4 }, { 3, 4 } };
int q = queries.Length;
// Perform queries
for (int i = 0; i < q; i++)
{
Console.WriteLine( performQueries(queries[i, 0],
queries[i, 1], prefix) );
}
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation of the approach
let N = 4 ;
// Function to return the length of the
// longest palindrome that can be formed
// using the characters in the range [l, r]
function performQueries(l, r, prefix)
{
// 0-based indexing
l--;
r--;
// Marks if there is an
// odd frequency character
let flag = false;
// Length of the longest palindrome
// possible from characters in range
let count = 0;
// Traverse for all characters
// and count their frequencies
for (let i = 0; i < 26; i++)
{
// Find the frequency in range 1 - r
let cnt = prefix[r][i];
// Exclude the frequencies in range 1 - (l - 1)
if (l > 0)
cnt -= prefix[l - 1][i];
// If frequency is odd, then add 1 less than
// the original frequency to make it even
if (cnt % 2 == 1)
{
flag = true;
count += cnt - 1;
}
// Else completely add if even
else
count += cnt;
}
// If any odd frequency character
// is present then add 1
if (flag)
count += 1;
return count;
}
// Function to pre-calculate the frequencies
// of the characters to reduce complexity
function preCalculate(s,prefix)
{
let n = s.length;
// Iterate and increase the count
for (let i = 0; i < n; i++)
{
prefix[i][s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
// Create a prefix type array
for (let i = 1; i < n; i++)
{
for (let j = 0; j < 26; j++)
prefix[i][j] += prefix[i - 1][j];
}
}
// Driver code
let s = "amim";
// Pre-calculate prefix array
let prefix = new Array(N);
for(let i = 0; i < 26; i++)
{
prefix[i] = new Array(26);
for(let j = 0; j < 26; j++)
{
prefix[i][j] = 0;
}
}
preCalculate(s, prefix);
let queries = [[ 1, 4 ], [ 3, 4 ]];
let q = queries.length;
// Perform queries
for (let i = 0; i < q; i++)
{
document.write( performQueries(queries[i][0],
queries[i][1], prefix) +"<br>");
}
// This code is contributed by patel2127
</script>
Producción:
3 1
Complejidad de tiempo: O (26 * N), ya que estamos usando bucles anidados para atravesar 26 * N veces. Donde N es la longitud de la string.
Espacio auxiliar: O(26*N), ya que estamos usando espacio adicional para la array de prefijos. Donde N es la longitud de la string.