Compruebe si una string se puede dividir en 3 substrings de modo que una de ellas sea una substring de las otras dos

Dada una string S que consta de N alfabetos en minúsculas, la tarea es verificar si es posible dividir la string S en tres substrings no vacías, de modo que Y sea la substring de las strings X y Z. Si es posible dividir la string S , imprima «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: S = «geekseekforgeeks»
Salida: Sí
Explicación:
La string dada S = «geeksforgeeks» se puede dividir en «geeks», «eek» y Z = «forgeeks».
La string «eeks» es una substring de las strings «geeks» y «forgeeks».

Entrada: S = “naturalxws”
Salida: No

Enfoque: el problema dado se puede resolver almacenando la frecuencia de caracteres únicos y observando el hecho de que si existe algún carácter que tenga una frecuencia de al menos 3 , entonces la string se puede dividir en 3 substrings que satisfagan las condiciones dadas. Siga los pasos a continuación para resolver el problema:

• Inicialice una array , digamos hash[] , para almacenar la frecuencia de los caracteres en la string S.
• Itere sobre los caracteres de la string y almacene la frecuencia de cada carácter presente en la string S en el arreglo hash[] .
• Recorra la array hash[] y si la frecuencia de cualquier carácter es mayor que 2, imprima «Sí» y salga del ciclo .
• Después de completar los pasos anteriores, si no existe tal carácter que tenga una frecuencia de al menos 3 , imprima «No» .

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 string S contains
// any character with frequency >= 3 or not
string freqCheck(string S, int N)
{
    // Stores frequency of characters
    int hash[26] = { 0 };
 
    // Iterate over the string
    for (int i = 0; i < N; i++) {
 
        // Update the frequency
        // of current character
        hash[S[i] - 'a']++;
    }
 
    // Iterate over the hash array
    for (int i = 0; i < 26; i++) {
 
        // If any character has
        // frequency >= 3
        if (hash[i] > 2) {
            return "Yes";
        }
    }
 
    // Otherwise
    return "No";
}
 
// Driver Code
int main()
{
    string S = "geekseekforgeeks";
    int N = S.length();
    cout << freqCheck(S, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to check if string S contains
// any character with frequency >= 3 or not
static String freqCheck(String S, int N)
{
     
    // Stores frequency of characters
    int hash[] = new int[26];
 
    // Iterate over the string
    for(int i = 0; i < N; i++)
    {
         
        // Update the frequency
        // of current character
        hash[S.charAt(i) - 'a']++;
    }
 
    // Iterate over the hash array
    for(int i = 0; i < 26; i++)
    {
         
        // If any character has
        // frequency >= 3
        if (hash[i] > 2)
        {
            return "Yes";
        }
    }
 
    // Otherwise
    return "No";
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "geekseekforgeeks";
    int N = S.length();
     
    System.out.println(freqCheck(S, N));
}
}
 
// This code is contributed by Kingash

# Python3 program for the above approach
 
# Function to check if string S contains
# any character with frequency >= 3 or not
def freqCheck(S, N):
 
    # Stores frequency of characters
    hash = [0] * 26
 
    # Iterate over the string
    for i in range(N):
 
        # Update the frequency
        # of current character
        hash[ord(S[i]) - ord('a')] += 1
 
    # Iterate over the hash array
    for i in range(26):
 
        # If any character has
        # frequency >= 3
        if (hash[i] > 2):
            return "Yes"
 
    # Otherwise
    return "No"
 
# Driver Code
if __name__ == "__main__":
 
    S = "geekseekforgeeks"
    N = len(S)
     
    print(freqCheck(S, N))
     
# This code is contributed by ukasp

// C# program for the above approach
using System;
 
class GFG{
     
// Function to check if string S contains
// any character with frequency >= 3 or not
static string freqCheck(string S, int N)
{
     
    // Stores frequency of characters
    int[] hash = new int[26];
 
    // Iterate over the string
    for(int i = 0; i < N; i++)
    {
         
        // Update the frequency
        // of current character
        hash[S[i] - 'a']++;
    }
 
    // Iterate over the hash array
    for(int i = 0; i < 26; i++)
    {
         
        // If any character has
        // frequency >= 3
        if (hash[i] > 2)
        {
            return "Yes";
        }
    }
 
    // Otherwise
    return "No";
}
 
// Driver code
static public void Main()
{
    string S = "geekseekforgeeks";
    int N = S.Length;
     
    Console.WriteLine(freqCheck(S, N));
}
}
 
// This code is contributed by offbeat

<script>
    // Javascript program for the above approach
 
// Function to check if string S contains
// any character with frequency >= 3 or not
function freqCheck(S, N){
 
    // Stores frequency of characters
    let hash = new Array(26).fill(0)
 
    // Iterate over the string
    for(let i = 0; i < N; i++){
 
        // Update the frequency
        // of current character
        hash[S.charCodeAt(i) - 'a'.charCodeAt(0)] += 1
    }
    // Iterate over the hash array
    for(let i = 0; i < 26; i++){
 
        // If any character has
        // frequency >= 3
        if (hash[i] > 2){
            return "Yes"
        }
    }
 
    // Otherwise
    return "No"
}
// Driver Code
 
    let S = "geekseekforgeeks"
    let N = S.length
     
    document.write(freqCheck(S, N))
     
// This code is contributed by gfgking
</script>

Yes

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