Divida la cuerda en tres subcuerdas palindrómicas con los cortes más tempranos posibles

Dada la string str , la tarea es verificar si es posible dividir la string S dada en tres substrings palindrómicas o no. Si son posibles múltiples respuestas, entonces imprima aquella en la que los cortes se hagan con menos índices. Si no existe tal partición posible, imprima “-1” .

Ejemplos:

Entrada: str = “aabbcdc”
Salida: aa bb cdc
Explicación:
Solo existe una partición posible {“aa”, “bb”, “cdc”}.

Entrada: str = “ababbcb”
Salida: a bab bcb 
Explicación: Las posibles divisiones son {“aba”, “b”, “bcb”} y {“a”, “bab”, “bcb”}. 
Dado que {“a”, “bab”, “bcb”} tiene divisiones en índices anteriores, es la respuesta requerida.

Enfoque: siga los pasos a continuación para resolver el problema:

1. Genere todas las substrings posibles de la string y verifique si la substring dada es palindrómica o no.
2. Si alguna substring está presente, almacene el último índice de una substring en un vector startPal , donde startPal almacenará el primer palíndromo a partir de 0 índices y terminando en el valor almacenado.
3. De manera similar al primer paso, genere toda la substring a partir del último índice de la string dada str y verifique si la substring dada es palíndromo o no. Si alguna substring está presente como una substring, almacene el último índice de una substring en el vector lastPal , donde lastPal almacenará el tercer palíndromo a partir del valor almacenado y terminando en (N – 1) el ^índice de la string dada str .
4. Invierta el vector lastPal para obtener el primer corte.
5. Ahora, itere dos bucles anidados, el bucle exterior elige el primer índice final de palíndromo de startPal y el bucle interior elige el tercer índice inicial de palíndromo de lastPal . Si el valor de startPal es menor que el valor de lastPal , guárdelo en el vector middlePal en forma de pares.
6. Ahora recorra el vector middlePal  y verifique si la substring entre el índice final del primer palíndromo y el índice inicial del tercer palíndromo es palíndromo o no. Si se determina que es cierto, entonces el primer palíndromo = s.substr(0, middlePal[i].first) , el tercer palíndromo = s.substr(middlePal[i].segundo, N – middlePal[i].segundo) y el resto string será la tercera cuerda.
7. Si las tres strings palindrómicas están presentes, imprima esa string. De lo contrario, imprima «-1» .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a string
// is palindrome or not
bool isPalindrome(string x)
{
    // Copy the string x to y
    string y = x;
 
    // Reverse the string y
    reverse(y.begin(), y.end());
 
    if (x == y) {
 
        // If string x equals y
        return true;
    }
 
    return false;
}
 
// Function to find three palindromes
// from the given string with earliest
// possible cuts
void Palindromes(string S, int N)
{
    // Stores index of palindrome
    // starting from left & right
    vector<int> startPal, lastPal;
 
    string start;
 
    // Store the indices for possible
    // palindromes from left
    for (int i = 0;
         i < S.length() - 2; i++) {
 
        // Push the current character
        start.push_back(S[i]);
 
        // Check for palindrome
        if (isPalindrome(start)) {
 
            // Insert the current index
            startPal.push_back(i);
        }
    }
 
    string last;
 
    // Stores the indexes for possible
    // palindromes from right
    for (int j = S.length() - 1;
         j >= 2; j--) {
 
        // Push the current character
        last.push_back(S[j]);
 
        // Check palindromic
        if (isPalindrome(last)) {
 
            // Insert the current index
            lastPal.push_back(j);
        }
    }
 
    // Sort the indexes for palindromes
    // from right in ascending order
    reverse(lastPal.begin(),
            lastPal.end());
 
    vector<pair<int, int> > middlePal;
 
    for (int i = 0;
         i < startPal.size(); i++) {
 
        for (int j = 0;
             j < lastPal.size(); j++) {
 
            // If the value of startPal
            // < lastPal value then
            // store it in middlePal
            if (startPal[i] < lastPal[j]) {
 
                // Insert the current pair
                middlePal.push_back(
                    { startPal[i],
                      lastPal[j] });
            }
        }
    }
 
    string res1, res2, res3;
    int flag = 0;
 
    // Traverse over the middlePal
    for (int i = 0;
         i < middlePal.size(); i++) {
 
        int x = middlePal[i].first;
        int y = middlePal[i].second;
 
        string middle;
 
        for (int k = x + 1; k < y; k++) {
            middle.push_back(S[k]);
        }
 
        // Check if the middle part
        // is palindrome
        if (isPalindrome(middle)) {
            flag = 1;
            res1 = S.substr(0, x + 1);
            res2 = middle;
            res3 = S.substr(y, N - y);
            break;
        }
    }
 
    // Print the three palindromic
    if (flag == 1) {
        cout << res1 << " "
             << res2 << " "
             << res3;
    }
 
    // Otherwise
    else
        cout << "-1";
}
 
// Driver Code
int main()
{
    // Given string str
    string str = "ababbcb";
 
    int N = str.length();
 
    // Function Call
    Palindromes(str, N);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
static class pair
{
  int first, second;
  public pair(int first,
              int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
static String reverse(String input)
{
  char[] a = input.toCharArray();
  int l, r = a.length - 1;
   
  for (l = 0; l < r; l++, r--)
  {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
  }
  return String.valueOf(a);
}
 
// Function to check if a String
// is palindrome or not
static boolean isPalindrome(String x)
{
  // Copy the String x to y
  String y = x;
 
  // Reverse the String y
  y = reverse(y);
 
  if (x.equals(y))
  {
    // If String x equals y
    return true;
  }
 
  return false;
}
 
// Function to find three palindromes
// from the given String with earliest
// possible cuts
static void Palindromes(String S,
                        int N)
{
  // Stores index of palindrome
  // starting from left & right
  Vector<Integer> startPal =
         new Vector<>();
  Vector<Integer> lastPal =
         new Vector<>();
 
  String start = "";
 
  // Store the indices for possible
  // palindromes from left
  for (int i = 0;
           i < S.length() - 2; i++)
  {
    // Push the current character
    start += S.charAt(i);
 
    // Check for palindrome
    if (isPalindrome(start))
    {
      // Insert the current index
      startPal.add(i);
    }
  }
 
  String last = "";
 
  // Stores the indexes for possible
  // palindromes from right
  for (int j = S.length() - 1;
           j >= 2; j--)
  {
    // Push the current character
    last += S.charAt(j);
 
    // Check palindromic
    if (isPalindrome(last))
    {
      // Insert the current index
      lastPal.add(j);
    }
  }
 
  // Sort the indexes for palindromes
  // from right in ascending order
  Collections.reverse(lastPal);
 
  Vector<pair> middlePal =
               new Vector<>();
   
  for (int i = 0;
           i < startPal.size(); i++)
  {
    for (int j = 0;
             j < lastPal.size(); j++)
    {
      // If the value of startPal
      // < lastPal value then
      // store it in middlePal
      if (startPal.get(i) <
          lastPal.get(j))
      {
        // Insert the current pair
        middlePal.add(new pair(startPal.get(i),
                               lastPal.get(j)));
      }
    }
  }
 
  String res1 = "",
         res2 = "", res3 = "";
  int flag = 0;
 
  // Traverse over the middlePal
  for (int i = 0;
           i < middlePal.size(); i++)
  {
    int x = middlePal.get(i).first;
    int y = middlePal.get(i).second;
    String middle = "";
 
    for (int k = x + 1; k < y; k++)
    {
      middle += S.charAt(k);
    }
 
    // Check if the middle part
    // is palindrome
    if (isPalindrome(middle))
    {
      flag = 1;
      res1 = S.substring(0, x + 1);
      res2 = middle;
      res3 = S.substring(y, N);
      break;
    }
  }
 
  // Print the three palindromic
  if (flag == 1)
  {
    System.out.print(res1 + " " +
                     res2 + " " + res3);
  }
 
  // Otherwise
  else
    System.out.print("-1");
}
 
// Driver Code
public static void main(String[] args)
{
  // Given String str
  String str = "ababbcb";
 
  int N = str.length();
 
  // Function Call
  Palindromes(str, N);
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to check if a string
# is palindrome or not
def isPalindrome(x):
     
    # Copy the x to y
    y = x
 
    # Reverse the y
    y = y[::-1]
 
    if (x == y):
 
        # If x equals y
        return True
         
    return False
 
# Function to find three palindromes
# from the given with earliest
# possible cuts
def Palindromes(S, N):
     
    # Stores index of palindrome
    # starting from left & right
    startPal, lastPal = [], []
 
    start = []
 
    # Store the indices for possible
    # palindromes from left
    for i in range(len(S) - 2):
 
        # Push the current character
        start.append(S[i])
 
        # Check for palindrome
        if (isPalindrome(start)):
 
            # Insert the current index
            startPal.append(i)
 
    last = []
 
    # Stores the indexes for possible
    # palindromes from right
    for j in range(len(S) - 1, 1, -1):
 
        # Push the current character
        last.append(S[j])
 
        # Check palindromic
        if (isPalindrome(last)):
 
            # Insert the current index
            lastPal.append(j)
 
    # Sort the indexes for palindromes
    # from right in ascending order
    lastPal = lastPal[::-1]
 
    middlePal = []
 
    for i in range(len(startPal)):
        for j in range(len(lastPal)):
 
            # If the value of startPal
            # < lastPal value then
            # store it in middlePal
            if (startPal[i] < lastPal[j]):
 
                # Insert the current pair
                middlePal.append([startPal[i],
                                   lastPal[j]])
 
    res1, res2, res3 = "", "", ""
    flag = 0
 
    # Traverse over the middlePal
    for i in range(len(middlePal)):
        x = middlePal[i][0]
        y = middlePal[i][1]
        #print(x,y)
 
        middle = ""
 
        for k in range(x + 1, y):
            middle += (S[k])
 
        # Check if the middle part
        # is palindrome
        if (isPalindrome(middle)):
            flag = 1
            res1 = S[0 : x + 1]
            res2 = middle
            res3 = S[y : N]
            #print(S,x,y,N)
            break
 
    # Print the three palindromic
    if (flag == 1):
        print(res1, res2, res3)
 
    # Otherwise
    else:
        print("-1")
 
# Driver Code
if __name__ == '__main__':
     
    # Given strr
    strr = "ababbcb"
 
    N = len(strr)
 
    # Function call
    Palindromes(strr, N)
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
public class pair
{
  public int first, second;
  public pair(int first,
              int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
static String reverse(String input)
{
  char[] a = input.ToCharArray();
  int l, r = a.Length - 1;
   
  for(l = 0; l < r; l++, r--)
  {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
  }
  return String.Join("",a);
}
 
// Function to check if a String
// is palindrome or not
static bool isPalindrome(String x)
{
   
  // Copy the String x to y
  String y = x;
 
  // Reverse the String y
  y = reverse(y);
 
  if (x.Equals(y))
  {
     
    // If String x equals y
    return true;
  }
  return false;
}
 
// Function to find three palindromes
// from the given String with earliest
// possible cuts
static void Palindromes(String S,
                        int N)
{
   
  // Stores index of palindrome
  // starting from left & right
  List<int> startPal = new List<int>();
  List<int> lastPal = new List<int>();
   
  String start = "";
 
  // Store the indices for possible
  // palindromes from left
  for(int i = 0;
          i < S.Length - 2; i++)
  {
     
    // Push the current character
    start += S[i];
 
    // Check for palindrome
    if (isPalindrome(start))
    {
       
      // Insert the current index
      startPal.Add(i);
    }
  }
 
  String last = "";
 
  // Stores the indexes for possible
  // palindromes from right
  for(int j = S.Length - 1;
          j >= 2; j--)
  {
     
    // Push the current character
    last += S[j];
 
    // Check palindromic
    if (isPalindrome(last))
    {
       
      // Insert the current index
      lastPal.Add(j);
    }
  }
   
  // Sort the indexes for palindromes
  // from right in ascending order
  lastPal.Reverse();
 
  List<pair> middlePal = new List<pair>();
   
  for(int i = 0;
          i < startPal.Count; i++)
  {
    for(int j = 0;
            j < lastPal.Count; j++)
    {
       
      // If the value of startPal
      // < lastPal value then
      // store it in middlePal
      if (startPal[i] < lastPal[j])
      {
         
        // Insert the current pair
        middlePal.Add(new pair(startPal[i],
                                lastPal[j]));
      }
    }
  }
 
  String res1 = "", res2 = "",
         res3 = "";
  int flag = 0;
 
  // Traverse over the middlePal
  for(int i = 0;
          i < middlePal.Count; i++)
  {
    int x = middlePal[i].first;
    int y = middlePal[i].second;
    String middle = "";
 
    for(int k = x + 1; k < y; k++)
    {
      middle += S[k];
    }
 
    // Check if the middle part
    // is palindrome
    if (isPalindrome(middle))
    {
      flag = 1;
      res1 = S.Substring(0, x + 1);
      res2 = middle;
      res3 = S.Substring(y);
      break;
    }
  }
 
  // Print the three palindromic
  if (flag == 1)
  {
    Console.Write(res1 + " " +
                  res2 + " " + res3);
  }
 
  // Otherwise
  else
    Console.Write("-1");
}
 
// Driver Code
public static void Main(String[] args)
{
   
  // Given String str
  String str = "ababbcb";
 
  int N = str.Length;
 
  // Function Call
  Palindromes(str, N);
}
}
 
// This code is contributed by Amit Katiyar

<script>
      // Function to check if a String
      // is palindrome or not
      function isPalindrome(x) {
        // Copy the String x to y
        var y = x;
 
        // Reverse the String y
        y = y.split("").reverse().join("");
 
        if (x === y) {
          // If String x equals y
          return true;
        }
        return false;
      }
 
      // Function to find three palindromes
      // from the given String with earliest
      // possible cuts
      function Palindromes(S, N) {
        // Stores index of palindrome
        // starting from left & right
        var startPal = [];
        var lastPal = [];
 
        var start = "";
 
        // Store the indices for possible
        // palindromes from left
        for (var i = 0; i < S.length - 2; i++) {
          // Push the current character
          start += S[i];
 
          // Check for palindrome
          if (isPalindrome(start)) {
            // Insert the current index
            startPal.push(i);
          }
        }
 
        var last = "";
 
        // Stores the indexes for possible
        // palindromes from right
        for (var j = S.length - 1; j >= 2; j--) {
          // Push the current character
          last += S[j];
 
          // Check palindromic
          if (isPalindrome(last)) {
            // Insert the current index
            lastPal.push(j);
          }
        }
 
        // Sort the indexes for palindromes
        // from right in ascending order
        lastPal.sort();
 
        var middlePal = [];
 
        for (var i = 0; i < startPal.length; i++) {
          for (var j = 0; j < lastPal.length; j++) {
            // If the value of startPal
            // < lastPal value then
            // store it in middlePal
            if (startPal[i] < lastPal[j]) {
              // Insert the current pair
              middlePal.push([startPal[i], lastPal[j]]);
            }
          }
        }
 
        var res1 = "",
          res2 = "",
          res3 = "";
        var flag = 0;
 
        // Traverse over the middlePal
        for (var i = 0; i < middlePal.length; i++) {
          var x = middlePal[i][0];
          var y = middlePal[i][1];
          var middle = "";
 
          for (var k = x + 1; k < y; k++) {
            middle += S[k];
          }
 
          // Check if the middle part
          // is palindrome
          if (isPalindrome(middle)) {
            flag = 1;
            res1 = S.substring(0, x + 1);
            res2 = middle;
            res3 = S.substring(y, N);
            break;
          }
        }
 
        // Print the three palindromic
        if (flag === 1) {
          document.write(res1 + " " + res2 + " " + res3);
        }
 
        // Otherwise
        else document.write("-1");
      }
 
      // Driver Code
      // Given String str
      var str = "ababbcb";
 
      var N = str.length;
 
      // Function Call
      Palindromes(str, N);
</script>

a bab bcb

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)