La substring más larga cuya substring no vacía no es prefijo o sufijo de la string dada

Dada una string S de longitud N , la tarea es encontrar la longitud de la substring X más larga de la string S tal que:

• Ninguna substring no vacía de X es un prefijo de S.
• Ninguna substring no vacía de X es un sufijo de S.
• Si no es posible tal string, imprima −1.

Ejemplos:

Entrada: S = “abcdefb”
Salida: 4
Explicación: cdef es la substring que cumple las condiciones.

Entrada: S = “cccc”
Salida: -1
Explicación: Ninguna substring puede satisfacer las condiciones.

Enfoque: Para resolver el problema, siga la siguiente observación:

Observaciones:

Dado que un prefijo comienza desde el comienzo de la string S y un sufijo comienza desde el final de una string S. Por lo tanto , la longitud máxima de la substring puede ser la longitud de la string S – 2 y no puede tener elementos que estén al principio o al final de la string.
Así que seleccione la substring que no tenga ningún carácter que sea el primero o el último carácter de la string. esta será la substring más grande que satisfaga las condiciones.

Siga los pasos mencionados para resolver el problema:

• Atraviesa la string desde i = 1 hasta el final de la string .
  • Compruebe si se encuentra algún carácter que no sea igual al primer y último carácter de la string.
  • Si se encuentra, considérelo parte de la substring resultante.
  • De lo contrario, no se incluiría en la substring.
• El resultado sería la longitud máxima de la substring que satisfaría las condiciones.

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest substring
int findLargest(string s)
{
  int maxi = -1;
  int sum = 0;
 
  // Loop to find the largest substring
  // satisfying the given conditions
  for (int i = 1; i < s.size() - 1; i++) {
    if (s[i] != s[0] && s[i] != s[s.length() - 1]) {
      sum++;
    }
    else {
      maxi = max(sum, maxi);
      sum = 0;
    }
  }
  maxi = max(sum, maxi);
  if (maxi == 0) {
    maxi = -1;
  }
 
  // Return the maximum length
  return maxi;
}
 
// Driver code
int main()
{
  string s = "abcdefb";
 
  // Function call
  cout << (findLargest(s));
 
  return 0;
}
 
// This code is contributed by rakeshsahni

// Java code to implement the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to find the largest substring
    public static int findLargest(String s)
    {
        int max = -1;
        int sum = 0;
 
        // Loop to find the largest substring
        // satisfying the given conditions
        for (int i = 1; i < s.length() - 1; i++) {
            if (s.charAt(i) != s.charAt(0)
                && s.charAt(i)
                       != s.charAt(s.length() - 1)) {
                sum++;
            }
            else {
                max = Math.max(sum, max);
                sum = 0;
            }
        }
        max = Math.max(sum, max);
        if (max == 0) {
            max = -1;
        }
 
        // Return the maximum length
        return max;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String s = "abcdefb";
 
        // Function call
        System.out.println(findLargest(s));
    }
}

# Python code to implement the above approach
 
# Function to find the largest substring
def findLargest(s):
 
  maxi = -1
  sum = 0
 
  # Loop to find the largest substring
  # satisfying the given conditions
  for i in range(1, len(s) - 1):
    if (s[i] != s[0] and s[i] != s[len(s) - 1]):
      sum += 1
     
    else:
      maxi = max(sum, maxi)
      sum = 0
     
  maxi = max(sum, maxi)
  if (maxi == 0):
    maxi = -1
 
  # Return the maximum length
  return maxi
 
# Driver code
if __name__ == "__main__":
   
  s = "abcdefb"
 
  # Function call
  print(findLargest(s))
   
  # This code is contributed by hrithikgarg03188.

// C# code to implement the above approach
using System;
 
public class GFG{
 
  // Function to find the largest substring
  public static int findLargest(string s)
  {
    int max = -1;
    int sum = 0;
 
    // Loop to find the largest substring
    // satisfying the given conditions
    for (int i = 1; i < s.Length - 1; i++) {
      if (s[i] != s[0] && s[i] != s[s.Length - 1]) {
        sum++;
      }
      else {
        max = Math.Max(sum, max);
        sum = 0;
      }
    }
    max = Math.Max(sum, max);
    if (max == 0) {
      max = -1;
    }
 
    // Return the maximum length
    return max;
  }
 
  // Driver code
  static public void Main (){
 
    string s = "abcdefb";
 
    // Function call
    Console.Write(findLargest(s));
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
       // JavaScript code for the above approach
 
       // Function to find the largest substring
       function findLargest(s) {
           let maxi = -1;
           let sum = 0;
 
           // Loop to find the largest substring
           // satisfying the given conditions
           for (let i = 1; i < s.length - 1; i++) {
               if (s[i] != s[0] && s[i] != s[s.length - 1]) {
                   sum++;
               }
               else {
                   maxi = Math.max(sum, maxi);
                   sum = 0;
               }
           }
           maxi = Math.max(sum, maxi);
           if (maxi == 0) {
               maxi = -1;
           }
 
           // Return the maximum length
           return maxi;
       }
 
       // Driver code
       let s = "abcdefb";
 
       // Function call
       document.write(findLargest(s));
 
   // This code is contributed by Potta Lokesh
   </script>

4

Complejidad temporal: O(N)
Espacio auxiliar: O(1)