Longitud mínima de substring cuya rotación genera una substring palindrómica

Dada una string str , la tarea es encontrar la longitud mínima de substring requerida para rotar que genera una substring palindrómica a partir de la string dada.

Ejemplos: 

Entrada: str = “abcbd” 
Salida: 0 
Explicación: No se puede generar ninguna substring palindrómica. No hay ningún carácter repetido en la string.
 

Entrada: str = “abcdeba” 
Salida: 3 
Explicación: Gire la substring “deb” para convertir la string dada en un bcb eda con una substring palindrómica “bcb”. 

Acercarse: 

• Si no se repite ningún carácter en la string, entonces no se puede generar una substring palindrómica.
• Para cada carácter repetido, verifique si el índice de su aparición anterior está dentro de uno o dos índices del índice actual. Si es así, entonces ya existe una substring palindrómica.
• De lo contrario, calcule la longitud de (índice actual – índice de la ocurrencia anterior – 1) .
• Devuelve el mínimo de todas las longitudes como la respuesta

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

// C++ Program to find the minimum
// length of substring whose rotation
// generates a palindromic substring
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// minimum length of substring
int count_min_length(string s)
{
 
    // Store the index of
    // previous occurrence
    // of the character
    int hash[26];
 
    // Variable to store
    // the maximum length
    // of substring
    int ans = INT_MAX;
 
    for (int i = 0; i < 26; i++)
        hash[i] = -1;
 
    for (int i = 0; i < s.size(); i++) {
        // If the current character
        // hasn't appeared yet
        if (hash[s[i] - 'a'] == -1)
            hash[s[i] - 'a'] = i;
        else {
            // If the character has occurred
            // within one or two previous
            // index, a palindromic substring
            // already exists
            if (hash[s[i] - 'a'] == i - 1
                || hash[s[i] - 'a'] == i - 2)
                return 0;
 
            // Update the maximum
            ans = min(ans,
                      i - hash[s[i] - 'a'] - 1);
 
            // Replace the previous
            // index of the character by
            // the current index
            hash[s[i] - 'a'] = i;
        }
    }
 
    // If character appeared
    // at least twice
    if (ans == INT_MAX)
        return -1;
 
    return ans;
}
// Driver Code
int main()
{
    string str = "abcdeba";
    cout << count_min_length(str);
}

// Java Program to find the minimum
// length of substring whose rotation
// generates a palindromic substring
import java.util.*;
import java.lang.*;
class GFG{
 
// Function to return the
// minimum length of substring
static int count_min_length(String s)
{
 
    // Store the index of
    // previous occurrence
    // of the character
    int[] hash = new int[26];
 
    // Variable to store
    // the maximum length
    // of substring
    int ans = Integer.MAX_VALUE;
 
    for (int i = 0; i < 26; i++)
        hash[i] = -1;
 
    for (int i = 0; i < s.length(); i++)
    {
        // If the current character
        // hasn't appeared yet
        if (hash[s.charAt(i) - 'a'] == -1)
            hash[s.charAt(i) - 'a'] = i;
        else
        {
            // If the character has occurred
            // within one or two previous
            // index, a palindromic substring
            // already exists
            if (hash[s.charAt(i) - 'a'] == i - 1 ||
                hash[s.charAt(i) - 'a'] == i - 2)
                return 0;
 
            // Update the maximum
            ans = Math.min(ans,
                       i - hash[s.charAt(i) - 'a'] - 1);
 
            // Replace the previous
            // index of the character by
            // the current index
            hash[s.charAt(i) - 'a'] = i;
        }
    }
 
    // If character appeared
    // at least twice
    if (ans == Integer.MAX_VALUE)
        return -1;
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    String str = "abcdeba";
 
    System.out.println(count_min_length(str));
}
}
 
// This code is contributed by offbeat

# Python3 program to find the minimum
# length of substring whose rotation
# generates a palindromic substring
import sys
 
INT_MAX = sys.maxsize;
 
# Function to return the
# minimum length of substring
def count_min_length(s):
 
    # Store the index of
    # previous occurrence
    # of the character
    hash = [0] * 26;
 
    # Variable to store
    # the maximum length
    # of substring
    ans = sys.maxsize;
 
    for i in range(26):
        hash[i] = -1;
 
    for i in range(len(s)):
         
        # If the current character
        # hasn't appeared yet
        if (hash[ord(s[i]) - ord('a')] == -1):
            hash[ord(s[i]) - ord('a')] = i;
        else :
             
            # If the character has occurred
            # within one or two previous
            # index, a palindromic substring
            # already exists
            if (hash[ord(s[i]) - ord('a')] == i - 1 or
                hash[ord(s[i]) - ord('a')] == i - 2) :
                return 0;
 
            # Update the maximum
            ans = min(ans, i - hash[ord(s[i]) -
                                    ord('a')] - 1);
 
            # Replace the previous
            # index of the character by
            # the current index
            hash[ord(s[i]) - ord('a')] = i;
 
    # If character appeared
    # at least twice
    if (ans == INT_MAX):
        return -1;
 
    return ans;
 
# Driver Code
if __name__ == "__main__":
 
    string = "abcdeba";
     
    print(count_min_length(string));
 
# This code is contributed by AnkitRai01

// C# Program to find the minimum
// length of substring whose rotation
// generates a palindromic substring
using System;
class GFG{
 
// Function to return the
// minimum length of substring
static int count_min_length(string s)
{
 
    // Store the index of
    // previous occurrence
    // of the character
    int[] hash = new int[26];
 
    // Variable to store
    // the maximum length
    // of substring
    int ans = int.MaxValue;
 
    for (int i = 0; i < 26; i++)
        hash[i] = -1;
 
    for (int i = 0; i < s.Length; i++)
    {
        // If the current character
        // hasn't appeared yet
        if (hash[s[i] - 'a'] == -1)
            hash[s[i] - 'a'] = i;
        else
        {
            // If the character has occurred
            // within one or two previous
            // index, a palindromic substring
            // already exists
            if (hash[s[i] - 'a'] == i - 1 ||
                hash[s[i] - 'a'] == i - 2)
                return 0;
 
            // Update the maximum
            ans = Math.Min(ans,
                      i - hash[s[i] - 'a'] - 1);
 
            // Replace the previous
            // index of the character by
            // the current index
            hash[s[i] - 'a'] = i;
        }
    }
 
    // If character appeared
    // at least twice
    if (ans == int.MaxValue)
        return -1;
 
    return ans;
}
 
// Driver code
public static void Main(string[] args)
{
    string str = "abcdeba";
 
    Console.WriteLine(count_min_length(str));
}
}
 
// This code is contributed by AnkitRai01

<script>
      // JavaScript Program to find the minimum
      // length of substring whose rotation
      // generates a palindromic substring
      // Function to return the
      // minimum length of substring
      function count_min_length(s) {
        // Store the index of
        // previous occurrence
        // of the character
        var hash = new Array(26).fill(0);
 
        // Variable to store
        // the maximum length
        // of substring
        var ans = 2147483648;
 
        for (var i = 0; i < 26; i++)
            hash[i] = -1;
 
        for (var i = 0; i < s.length; i++) {
          // If the current character
          // hasn't appeared yet
          if (hash[s[i].charCodeAt(0) - "a".charCodeAt(0)] == -1)
            hash[s[i].charCodeAt(0) - "a".charCodeAt(0)] = i;
          else {
            // If the character has occurred
            // within one or two previous
            // index, a palindromic substring
            // already exists
            if (
              hash[s[i].charCodeAt(0) - "a".charCodeAt(0)] == i - 1 ||
              hash[s[i].charCodeAt(0) - "a".charCodeAt(0)] == i - 2
            )
              return 0;
 
            // Update the maximum
            ans = Math.min(
              ans,
              i - hash[s[i].charCodeAt(0) - "a".charCodeAt(0)] - 1
            );
 
            // Replace the previous
            // index of the character by
            // the current index
            hash[s[i].charCodeAt(0) - "a".charCodeAt(0)] = i;
          }
        }
 
        // If character appeared
        // at least twice
        if (ans === 2147483648) return -1;
 
        return ans;
      }
 
      // Driver code
      var str = "abcdeba";
 
      document.write(count_min_length(str));
</script>

3

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O (N) tiempo 
Espacio auxiliar: O (26), ya que estamos usando espacio adicional para el hash.