Dada una string numérica S , la tarea es encontrar la substring no vacía más larga que se pueda convertir en palíndromo .
Ejemplos:
Entrada: S = “3242415”
Salida: 5
Explicación: “24241” es la substring más larga que se puede convertir en la string palindrómica “24142”.Entrada: S = «213123»
Salida: 6
Explicación: «213123» tal substring que se puede convertir a la string palindrómica «231132».
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las substrings posibles y, para cada substring, verificar si se puede convertir en un palíndromo o no contando los caracteres en cada substring y verificar si solo está presente un carácter impar frecuente o ninguno. no.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea de resolver este problema es utilizar el enmascaramiento de bits y la programación dinámica . Se puede formar un palíndromo si la cuenta de cada número incluido (excepto quizás uno) es par. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable entera, digamos mask . Un bit en nuestra máscara es 0 si la cuenta del número correspondiente es par y 1 si es impar .
- Atraviese la string y, mientras la atraviesa, realice un seguimiento de los recuentos pares/impares en la máscara variable .
- Si se vuelve a encontrar la misma máscara , el subarreglo entre la primera posición (exclusivo) y la posición actual (inclusive) con la misma máscara tiene todos los números con el conteo par.
- Deje que el tamaño de la substring se almacene en una variable, digamos res .
- Inicialice una array, digamos dp[] , para rastrear la posición más pequeña (primera) de cada máscara de tamaño 1024, ya que la entrada solo contiene 10 dígitos («0123456789»), y solo puede haber 2^10 o 1024 variaciones de bit máscaras
- El tamaño de la substring se puede calcular restándolo de la posición actual. Tenga en cuenta que la posición para la máscara cero es -1, ya que se debe incluir el primer carácter.
- Además, verifique todas las máscaras que sean diferentes de la actual en un bit . En otras palabras, si dos máscaras difieren en un bit, eso significa que hay un recuento impar en la substring.
- Imprime res como la longitud de la substring más larga.
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 the Longest
// substring that can be made a
// palindrome by swapping of characters
int longestSubstring(string s)
{
// Initialize dp array of size 1024
int dp[1024];
// Initializeing dp array with length of s
fill(dp, dp + 1024, s.size());
// Initializing mask and res
int res = 0, mask = 0;
dp[0] = -1;
// Traverse the string
for (int i = 0; i < s.size(); ++i)
{
// Find the mask of the current character
mask ^= 1 << (s[i] - 48);
// Finding the length of the longest
// substring in s which is a
// palindrome for even count
res = max(res, i - dp[mask]);
// Finding the length of the longest
// substring in s which is a
// palindrome for one odd count
for (int j = 0; j <= 9; ++j)
// Finding maximum length of
// substring having one odd count
res = max(res, i - dp[mask ^ (1 << j)]);
// dp[mask] is minimum of
// current i and dp[mask]
dp[mask] = min(dp[mask], i);
}
// Return longest length of the substring
// which forms a palindrome with swaps
return res;
}
// Driver Code
int main()
{
// Input String
string s = "3242415";
// Function Call
cout << longestSubstring(s);
return 0;
}
// This code is contributed by subhammahato348.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the Longest
// substring that can be made a
// palindrome by swapping of characters
public static int longestSubstring(String s)
{
// Initialize dp array of size 1024
int dp[] = new int[1024];
// Initializeing dp array with length of s
Arrays.fill(dp, s.length());
// Initializing mask and res
int res = 0, mask = 0;
dp[0] = -1;
// Traverse the string
for (int i = 0; i < s.length(); ++i) {
// Find the mask of the current character
mask ^= 1 << (s.charAt(i) - '0');
// Finding the length of the longest
// substring in s which is a
// palindrome for even count
res = Math.max(res, i - dp[mask]);
// Finding the length of the longest
// substring in s which is a
// palindrome for one odd count
for (int j = 0; j <= 9; ++j)
// Finding maximum length of
// substring having one odd count
res = Math.max(res,
i - dp[mask ^ (1 << j)]);
// dp[mask] is minimum of
// current i and dp[mask]
dp[mask] = Math.min(dp[mask], i);
}
// Return longest length of the substring
// which forms a palindrome with swaps
return res;
}
// Driver Code
public static void main(String[] args)
{
// Input String
String s = "3242415";
// Function Call
System.out.println(longestSubstring(s));
}
}
Python3
# Python3 program for the above approach
# Function to find the Longest
# substring that can be made a
# palindrome by swapping of characters
def longestSubstring(s):
# Initialize dp array of size 1024
dp = [1024 for i in range(1024)]
# Initializeing dp array with length of s
# Arrays.fill(dp, s.length());
# Initializing mask and res
res, mask = 0, 0
dp[0] = -1
# Traverse the string
for i in range(len(s)):
# Find the mask of the current character
mask ^= 1 << (ord(s[i]) - ord('0'))
# Finding the length of the longest
# substring in s which is a
# palindrome for even count
res = max(res, i - dp[mask])
# Finding the length of the longest
# substring in s which is a
# palindrome for one odd count
for j in range(10):
# Finding maximum length of
# substring having one odd count
res = max(res, i - dp[mask ^ (1 << j)])
# dp[mask] is minimum of
# current i and dp[mask]
dp[mask] = min(dp[mask], i)
# Return longest length of the substring
# which forms a palindrome with swaps
return res
# Driver Code
if __name__ == '__main__':
# Input String
s = "3242415"
# Function Call
print(longestSubstring(s))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the Longest
// substring that can be made a
// palindrome by swapping of characters
public static int longestSubstring(string s)
{
// Initialize dp array of size 1024
int []dp = new int[1024];
// Initializeing dp array with length of s
for (int i = 0; i < 1024; ++i)
{
dp[i] = s.Length;
}
// Initializing mask and res
int res = 0, mask = 0;
dp[0] = -1;
// Traverse the string
for (int i = 0; i < s.Length; i++)
{
// Find the mask of the current character
mask = mask ^ (1 << (s[i] - '0'));
// Finding the length of the longest
// substring in s which is a
// palindrome for even count
res = Math.Max(res, i - dp[mask]);
// Finding the length of the longest
// substring in s which is a
// palindrome for one odd count
for (int j = 0; j < 10; j++)
{
// Finding maximum length of
// substring having one odd count
res = Math.Max(res,i - dp[mask ^ (1 << j)]);
}
// dp[mask] is minimum of
// current i and dp[mask]
dp[mask] = Math.Min(dp[mask], i);
}
// Return longest length of the substring
// which forms a palindrome with swaps
return res;
}
// Driver Code
public static void Main(string[] args)
{
// Input String
string s = "3242415";
// Function Call
Console.WriteLine(longestSubstring(s));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to find the Longest
// substring that can be made a
// palindrome by swapping of characters
function longestSubstring(s)
{
// Initialize dp array of size 1024
let dp = new Array(1024).fill(1);
// Initializing mask and res
let res = 0, mask = 0;
dp[0] = -1;
// Traverse the string
for(let i = 0; i < s.length; ++i)
{
// Find the mask of the current character
mask ^= 1 << (s[i] - '0');
// Finding the length of the longest
// substring in s which is a
// palindrome for even count
res = Math.max(res, i - dp[mask]);
// Finding the length of the longest
// substring in s which is a
// palindrome for one odd count
for(let j = 0; j <= 9; ++j)
// Finding maximum length of
// substring having one odd count
res = Math.max(res,
i - dp[mask ^ (1 << j)]);
// dp[mask] is minimum of
// current i and dp[mask]
dp[mask] = Math.min(dp[mask], i);
}
// Return longest length of the substring
// which forms a palindrome with swaps
return res;
}
// Driver Code
// Input String
let s = "3242415";
// Function Call
document.write(longestSubstring(s));
// This code is contributed by splevel62
</script>
Producción:
5
Complejidad de tiempo: O(10*N)
Espacio auxiliar: O(1024)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA