Substring de longitud uniforme máxima que es la permutación de un palíndromo

Dada una string , la tarea es encontrar la longitud máxima de la substring que se puede organizar en un palíndromo (es decir, al menos una de sus permutaciones es un palíndromo). Tenga en cuenta que la substring debe tener una longitud uniforme.

Ejemplos:

Entrada: str = «124565463»
Salida: 6
«456546» es la substring válida

Entrada: str = «122313»
Salida: 6

Enfoque: use dos variables: inicio (inclusivo) y final (exclusivo) para realizar un seguimiento del índice inicial y final de la substring actual que se está considerando en la string dada. También use un diccionario llamado count que mantiene el registro de cuántas veces aparece un carácter en la substring actual. Ahora, hay dos casos posibles para una substring:

1. Si la longitud de la substring es impar, entonces no se puede considerar en la solución final.
2. Si la longitud de la substring es par, entonces puede ser una posible solución solo si cada carácter en esa substring aparece un número par de veces, lo que se puede hacer usando el conteo del diccionario . Comprobamos si cada carácter aparece un número par de veces o no. En caso afirmativo, lo incluimos como una de las posibles soluciones. Luego, formamos la siguiente substring al incluir el siguiente carácter en la string, lo que se puede hacer simplemente incrementando end y verificando recursivamente si se puede formar una substring con mayor longitud que satisfaga las condiciones dadas y devuelva el máximo de todos los posibles. soluciones

A continuación se muestra la implementación del enfoque anterior:

// C++ code to find the maximum length of 
// sub-string (of even length) which can be
// arranged into a Palindrome
#include <bits/stdc++.h>
using namespace std;
  
unordered_map<int, int> countt;
  
// function that returns true if the given
// sub-string can be arranged into a Palindrome
bool canBePalindrome(unordered_map<int, int> &countt) 
{
    for (auto key : countt)
    {
        if (key.second & 1) return false;
    }
    return true;
}
  
// This function returns the maximum length of
// the sub-string (of even length) which can be
// arranged into a Palindrome
int maxPal(string str,
           unordered_map<int, int> &countt,
           int start, int end)
{
      
    // If we reach end of the string
    if (end == str.length()) 
    {
  
        // if string is of even length
        if ((end - start) % 2 == 0)
  
            // if string can be arranged into a
            // palindrome
            if (canBePalindrome(countt)) return end - start;
  
        return 0;
    } 
    else 
    {
  
        // Even length sub-string
        if ((end - start) % 2 == 0) 
        {
  
            // Check if current sub-string can be
            // arranged into a palindrome
            if (canBePalindrome(countt))
            {
                countt[str[end]]++;
                return max(end - start, maxPal(str, countt, 
                                               start, end + 1));
            } 
            else
            {
                countt[str[end]]++;
                return maxPal(str, countt, start, end + 1);
            }
        }
  
        // Odd length sub-string
        else
        {
            countt[str[end]]++;
            unordered_map<int, int> c(countt.begin(), 
                                      countt.end());
            int length = maxPal(str, c, start, end + 1);
  
            countt[str[end]]--;
            countt[str[start]]--;
            return max(length, maxPal(str, countt, 
                                      start + 1, end));
        }
    }
}
  
// Driver code
int main(int argc, char const *argv[])
{
    string str = "124565463";
    int start = 0, end = 0;
  
    cout << maxPal(str, countt, start, end) << endl;
    return 0;
}
  
// This code is contributed by
// sanjeev2552

// Java code to find the maximum length of 
// sub-string (of even length) which can be 
// arranged into a Palindrome 
import java.io.*;
import java.util.*;
  
class GFG 
{
  
    static HashMap<Integer, Integer> count = new HashMap<>();
  
    // function that returns true if the given
    // sub-string can be arranged into a Palindrome
    static boolean canBePalindrome(HashMap<Integer, Integer> count)
    {
        for (HashMap.Entry<Integer, Integer> entry : count.entrySet())
            if ((entry.getValue() & 1) == 1)
                return false;
        return true;
    }
  
    // This function returns the maximum length of
    // the sub-string (of even length) which can be
    // arranged into a Palindrome
    static int maxPal(String str, int start, int end, 
                       HashMap<Integer, Integer> count)
    {
  
        // If we reach end of the string
        if (end == str.length())
        {
  
            // if string is of even length
            if ((end - start) % 2 == 0)
  
                // if string can be arranged into a
                // palindrome
                if (canBePalindrome(count))
                    return end - start;
  
            return 0;
        } 
        else
        {
  
            // Even length sub-string
            if ((end - start) % 2 == 0) 
            {
  
                // Check if current sub-string can be
                // arranged into a palindrome
                if (canBePalindrome(count))
                {
                    count.put((int) str.charAt(end),
                    count.get((int) str.charAt(end)) ==
                    null ? 1 : count.get((int) str.charAt(end)) + 1);
                    return Math.max(end - start, 
                            maxPal(str, start, end + 1, count));
                }
                else
                {
                    count.put((int) str.charAt(end),
                    count.get((int) str.charAt(end)) ==
                    null ? 1 : count.get((int) str.charAt(end)) + 1);
                    return maxPal(str, start, end + 1, count);
                }
            }
  
            // Odd length sub-string
            else
            {
                count.put((int) str.charAt(end),
                count.get((int) str.charAt(end)) == 
                null ? 1 : count.get((int) str.charAt(end)) + 1);
                HashMap<Integer, Integer> c = new HashMap<>(count);
  
                int length = maxPal(str, start, end + 1, c);
  
                count.put((int) str.charAt(end),
                count.get((int) str.charAt(end)) ==
                null ? -1 : count.get((int) str.charAt(end)) - 1);
                  
                count.put((int) str.charAt(start),
                count.get((int) str.charAt(start)) ==
                null ? -1 : count.get((int) str.charAt(start)) - 1);
  
                return Math.max(length, maxPal(str, 
                            start + 1, end, count));
            }
        }
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        String str = "124565463";
        int start = 0, end = 0;
        System.out.println(maxPal(str, start, end, count));
    }
}
  
// This code is contributed by
// sanjeev2552

# Python3 code to find the maximum length of sub-string 
# (of even length) which can be arranged into a Palindrome
  
from collections import defaultdict
  
# function that returns true if the given 
# sub-string can be arranged into a Palindrome
def canBePalindrome(count):    
    for key in count:
        if count[key] % 2 != 0:
            return False            
    return True
      
# This function returns the maximum length of 
# the sub-string (of even length) which can be 
# arranged into a Palindrome
def maxPal(string, count, start, end):
      
    # If we reach end of the string
    if end == len(string):
  
        # if string is of even length
        if (end-start) % 2 == 0:
  
            # if string can be arranged into a
            # palindrome
            if canBePalindrome(count) == True:
                return end-start
                  
        return 0
          
    else:
          
        # Even length sub-string
        if (end-start) % 2 == 0:
              
            # Check if current sub-string can be 
            # arranged into a palindrome
            if canBePalindrome(count) == True:
                count[string[end]] += 1
                return max(end-start, maxPal(string, count, start, end + 1))
                  
            else:
                count[string[end]] += 1
                return maxPal(string, count, start, end + 1)
          
        # Odd length sub-string  
        else:
              
            count[string[end]] += 1
            length = maxPal(string, count.copy(), start, end + 1)
              
            count[string[end]] -= 1
            count[string[start]] -= 1
            return max(length, maxPal(string, count, start + 1, end))
              
# Driver code
string = '124565463'
start, end = 0, 0
count = defaultdict(lambda : 0)
  
print(maxPal(string, count, start, end))

6