Dada una string S de longitud N que solo contiene letras en minúsculas. Encuentre la longitud de la substring más larga de S tal que los caracteres en ella se puedan reorganizar para formar un palíndromo .
Ejemplos:
Entrada: S = “aabe”
Salida: 3
Explicación:
La substring “aab” se puede reorganizar para formar “aba”, que es una substring palindrómica.
Dado que la longitud de «aab» es 3, la salida es 3.
Tenga en cuenta que «a», «aa», «b» y «e» se pueden organizar para formar strings palindrómicas, pero no son más largas que «aab».Entrada: S = “adbabd”
Salida: 6
Explicación:
La string completa “adbabd” se puede reorganizar para formar una substring palindrómica. Un arreglo posible es «abddba».
Por lo tanto, la longitud de salida de la string, es decir, 6.
Enfoque ingenuo: la idea es generar todas las substrings posibles y llevar la cuenta de cada carácter que contiene. Inicialice la respuesta con el valor 0. Si el recuento de cada carácter es par con un carácter impar como máximo, la substring se puede reorganizar para formar una string palindrómica. Si una substring satisface esta propiedad, actualice la respuesta. Imprime la longitud máxima después de los pasos anteriores.
Complejidad de Tiempo: O(N 3 * 26)
Espacio Auxiliar: O(N 2 * 26)
Enfoque eficiente: la idea es observar que la string es un palíndromo si , como máximo , un carácter aparece un número impar de veces. Por lo tanto, no es necesario mantener el recuento total de cada carácter. Solo saber que está ocurriendo un número par o impar de veces es suficiente. Para hacer esto, use el enmascaramiento de bits ya que el conteo de letras en minúsculas es solo 26.
- Defina una máscara de variable de máscara de bits que rastree si la aparición de cada carácter es par o impar.
- Cree un índice de diccionario que realice un seguimiento del índice de cada máscara de bits.
- Recorre la string dada S . Primero, convierta los caracteres de ‘a’ – ‘z’ a 0 – 25 y almacene este valor en una variable temp . Para cada aparición del carácter, tome Bitwise XOR de 2 temp con la máscara .
- Si el carácter aparece un número par de veces, su bit en la máscara estará desactivado ; de lo contrario, estará activado . Si la máscara no está actualmente en el índice , simplemente asigne el índice actual i a la máscara de máscara de bits en el índice .
- Si la máscara está presente en el índice , significa que desde el índice [máscara] hasta i , la aparición de todos los caracteres es uniforme, lo que es adecuado para una substring palindrómica. Por lo tanto, actualice la respuesta si la longitud de este segmento desde el índice [máscara] hasta i es mayor que la respuesta.
- Para verificar la substring con un carácter que aparece un número impar de veces, itere una variable j sobre [0, 25] . Almacene Bitwise XOR de x con 2 j en mask2 .
- Si mask2 está presente en el índice , esto significa que este carácter aparece un número impar de veces y todos los caracteres aparecen un número par de veces en el segmento index[mask2] a i , que también es una condición adecuada para una string palindrómica. Por lo tanto, actualice nuestra respuesta con la longitud de esta substring si es mayor que la respuesta .
- Imprima la longitud máxima de la substring después de los pasos anteriores.
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 get the length of longest
// substring whose characters can be
// arranged to form a palindromic string
int longestSubstring(string s, int n)
{
// To keep track of the last
// index of each xor
map<int, int> index;
// Initialize answer with 0
int answer = 0;
int mask = 0;
index[mask] = -1;
// Now iterate through each character
// of the string
for(int i = 0; i < n; i++)
{
// Convert the character from
// [a, z] to [0, 25]
int temp = (int)s[i] - 97;
// Turn the temp-th bit on if
// character occurs odd number
// of times and turn off the temp-th
// bit off if the character occurs
// ever number of times
mask ^= (1 << temp);
// If a mask is present in the index
// Therefore a palindrome is
// found from index[mask] to i
if (index[mask])
{
answer = max(answer,
i - index[mask]);
}
// If x is not found then add its
// position in the index dict.
else
index[mask] = i;
// Check for the palindrome of
// odd length
for(int j = 0; j < 26; j++)
{
// We cancel the occurrence
// of a character if it occurs
// odd number times
int mask2 = mask ^ (1 << j);
if (index[mask2])
{
answer =max(answer,
i - index[mask2]);
}
}
}
return answer;
}
// Driver code
int main ()
{
// Given String
string s = "adbabd";
// Length of given string
int n = s.size();
// Function call
cout << (longestSubstring(s, n));
}
// This code is contributed by Stream_Cipher
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to get the length of longest
// substring whose characters can be
// arranged to form a palindromic string
static int longestSubstring(String s, int n)
{
// To keep track of the last
// index of each xor
Map<Integer, Integer> index = new HashMap<>();
// Initialize answer with 0
int answer = 0;
int mask = 0;
index.put(mask, -1);
// Now iterate through each character
// of the string
for(int i = 0; i < n; i++)
{
// Convert the character from
// [a, z] to [0, 25]
int temp = (int)s.charAt(i) - 97;
// Turn the temp-th bit on if
// character occurs odd number
// of times and turn off the temp-th
// bit off if the character occurs
// ever number of times
mask ^= (1 << temp);
// If a mask is present in the index
// Therefore a palindrome is
// found from index[mask] to i
if (index.containsKey(mask))
{
answer = Math.max(answer,
i - index.get(mask));
}
// If x is not found then add its
// position in the index dict.
else
index.put(mask,i);
// Check for the palindrome of
// odd length
for (int j = 0;j < 26; j++)
{
// We cancel the occurrence
// of a character if it occurs
// odd number times
int mask2 = mask ^ (1 << j);
if (index.containsKey(mask2))
{
answer = Math.max(answer,
i - index.get(mask2));
}
}
}
return answer;
}
// Driver code
public static void main (String[] args)
{
// Given String
String s = "adbabd";
// Length of given string
int n = s.length();
// Function call
System.out.print(longestSubstring(s, n));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to get the length of longest # substring whose characters can be # arranged to form a palindromic string def longestSubstring(s: str, n: int): # To keep track of the last # index of each xor index = dict() # Initialize answer with 0 answer = 0 mask = 0 index[mask] = -1 # Now iterate through each character # of the string for i in range(n): # Convert the character from # [a, z] to [0, 25] temp = ord(s[i]) - 97 # Turn the temp-th bit on if # character occurs odd number # of times and turn off the temp-th # bit off if the character occurs # ever number of times mask ^= (1 << temp) # If a mask is present in the index # Therefore a palindrome is # found from index[mask] to i if mask in index.keys(): answer = max(answer, i - index[mask]) # If x is not found then add its # position in the index dict. else: index[mask] = i # Check for the palindrome of # odd length for j in range(26): # We cancel the occurrence # of a character if it occurs # odd number times mask2 = mask ^ (1 << j) if mask2 in index.keys(): answer = max(answer, i - index[mask2]) return answer # Driver Code # Given String s = "adbabd" # Length of given string n = len(s) # Function call print(longestSubstring(s, n))
C#
// C# program for the above approach
using System.Collections.Generic;
using System;
class GFG{
// Function to get the length of longest
// substring whose characters can be
// arranged to form a palindromic string
static int longestSubstring(string s, int n)
{
// To keep track of the last
// index of each xor
Dictionary<int,
int> index = new Dictionary<int,
int>();
// Initialize answer with 0
int answer = 0;
int mask = 0;
index[mask] = -1;
// Now iterate through each character
// of the string
for(int i = 0; i < n; i++)
{
// Convert the character from
// [a, z] to [0, 25]
int temp = (int)s[i] - 97;
// Turn the temp-th bit on if
// character occurs odd number
// of times and turn off the temp-th
// bit off if the character occurs
// ever number of times
mask ^= (1 << temp);
// If a mask is present in the index
// Therefore a palindrome is
// found from index[mask] to i
if (index.ContainsKey(mask) == true)
{
answer = Math.Max(answer,
i - index[mask]);
}
// If x is not found then add its
// position in the index dict.
else
index[mask] = i;
// Check for the palindrome of
// odd length
for(int j = 0; j < 26; j++)
{
// We cancel the occurrence
// of a character if it occurs
// odd number times
int mask2 = mask ^ (1 << j);
if (index.ContainsKey(mask2) == true)
{
answer = Math.Max(answer,
i - index[mask2]);
}
}
}
return answer;
}
// Driver code
public static void Main ()
{
// Given String
string s = "adbabd";
// Length of given string
int n = s.Length;
// Function call
Console.WriteLine(longestSubstring(s, n));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript program for the above approach
// Function to get the length of longest
// substring whose characters can be
// arranged to form a palindromic string
function longestSubstring(s, n)
{
// To keep track of the last
// index of each xor
var index = new Map();
// Initialize answer with 0
var answer = 0;
var mask = 0;
index[mask] = -1;
// Now iterate through each character
// of the string
for(var i = 0; i < n; i++)
{
// Convert the character from
// [a, z] to [0, 25]
var temp = s[i].charCodeAt(0) - 97;
// Turn the temp-th bit on if
// character occurs odd number
// of times and turn off the temp-th
// bit off if the character occurs
// ever number of times
mask ^= (1 << temp);
// If a mask is present in the index
// Therefore a palindrome is
// found from index[mask] to i
if (index[mask])
{
answer = Math.max(answer,
i - index[mask]);
}
// If x is not found then add its
// position in the index dict.
else
index[mask] = i;
// Check for the palindrome of
// odd length
for(var j = 0; j < 26; j++)
{
// We cancel the occurrence
// of a character if it occurs
// odd number times
var mask2 = mask ^ (1 << j);
if (index[mask2])
{
answer = Math.max(answer,
i - index[mask2]);
}
}
}
return answer;
}
// Driver code
// Given String
var s = "adbabd";
// Length of given string
var n = s.length;
// Function call
document.write(longestSubstring(s, n));
// This code is contributed by rrrtnx.
</script>
Producción:
6
Complejidad de Tiempo: O(N * 26)
Espacio Auxiliar: O(N * 26)
Publicación traducida automáticamente
Artículo escrito por aditya_panwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA