Compruebe si existen dos mismas subsecuencias en una string o no

Dada una string, la tarea es verificar si existen dos subsecuencias iguales en la string dada. Se dice que dos subsecuencias son iguales si tienen los mismos caracteres dispuestos en el mismo orden lexicográfico pero la posición de los caracteres difiere de la de la string original. 
Ejemplos: 
 

Entrada: str = «geeksforgeeks» 
Salida: SÍ 
Dos posibles subsecuencias son «geeks» y «geeks». 
Entrada: str = “bhuvan” 
Salida: NO

Enfoque: El enfoque para resolver este problema es verificar si algún personaje aparece más de una vez. Dado que la longitud mínima de la subsecuencia coincidente puede ser 1, por lo tanto, si un carácter aparece en una string más de una vez, entonces son posibles dos subsecuencias similares. Inicialice una array freq[] de longitud 26. Repita la string e incremente la frecuencia de los caracteres. Itere sobre la array de frecuencias y verifique si freq[i] para cualquier i en el rango de 0-26 es mayor que 1, entonces es posible. 
A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program to Check if
// similar subsequences exist or not
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if similar subsequences
// occur in a string or not
bool check(string s, int l)
{
 
    int freq[26] = { 0 };
    // iterate and count the frequency
    for (int i = 0; i < l; i++) {
        freq[s[i] - 'a']++; // counting frequency of the letters
    }
 
    // check if frequency is more
    // than once of any character
    for (int i = 0; i < 26; i++) {
        if (freq[i] >= 2)
            return true;
    }
    return false;
}
// Driver Code
int main()
{
    string s = "geeksforgeeks";
    int l = s.length();
    if (check(s, l))
        cout << "YES";
    else
        cout << "NO";
 
    return 0;
}

// Java program to Check
// if similar subsequences
// exist or not
import java.io.*;
import java.util.*;
import java.util.Arrays;
 
class GFG
{
// Function to check if
// similar subsequences
// occur in a string or not
static boolean check(String s,
                     int l)
{
    int freq[] = new int[26];
    Arrays.fill(freq, 0);
     
    // iterate and count
    // the frequency
    for (int i = 0; i < l; i++)
    {
        // counting frequency
        // of the letters
        freq[s.charAt(i) - 'a']++;
    }
 
    // check if frequency is more
    // than once of any character
    for (int i = 0; i < 26; i++)
    {
        if (freq[i] >= 2)
            return true;
    }
    return false;
}
 
// Driver Code
public static void main(String args[])
{
    String s = "geeksforgeeks";
    int l = s.length();
    if (check(s, l))
        System.out.print("YES");
    else
        System.out.print("NO");
}
}

# Python 3 program to Check if
# similar subsequences exist or not
 
# Function to check if similar subsequences
# occur in a string or not
def check(s, l):
    freq = [0 for i in range(26)]
     
    # iterate and count the frequency
    for i in range(l):
         
        # counting frequency of the letters
        freq[ord(s[i]) - ord('a')] += 1
         
    # check if frequency is more
    # than once of any character
    for i in range(26):
        if (freq[i] >= 2):
            return True
 
    return False
 
# Driver Code
if __name__ == '__main__':
    s = "geeksforgeeks"
    l = len(s)
    if (check(s, l)):
        print("YES")
    else:
        print("NO")
 
# This code is contributed by
# Sahil_Shelangia

// C# program to Check if similar subsequences
// exist or not
using System;
using System.Collections.Generic;            
 
class GFG
{
     
// Function to check if similar subsequences
// occur in a string or not
static bool check(String s, int l)
{
    int []freq = new int[26];
     
    // iterate and count the frequency
    for (int i = 0; i < l; i++)
    {
        // counting frequency of the letters
        freq[s[i] - 'a']++;
    }
 
    // check if frequency is more
    // than once of any character
    for (int i = 0; i < 26; i++)
    {
        if (freq[i] >= 2)
            return true;
    }
    return false;
}
 
// Driver Code
public static void Main(String []args)
{
    String s = "geeksforgeeks";
    int l = s.Length;
    if (check(s, l))
        Console.WriteLine("YES");
    else
        Console.WriteLine("NO");
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program to Check
// if similar subsequences
// exist or not
 
// Function to check if
// similar subsequences
// occur in a string or not
function check(s, l)
{
    let freq = new Array(26).fill(0);
       
    // iterate and count
    // the frequency
    for (let i = 0; i < l; i++)
    {
        // counting frequency
        // of the letters
        freq[s[i].charCodeAt() - 'a'.charCodeAt()]++;
    }
   
    // check if frequency is more
    // than once of any character
    for (let i = 0; i < 26; i++)
    {
        if (freq[i] >= 2)
            return true;
    }
    return false;
}
  
// Driver Code
 
    let s = "geeksforgeeks";
    let l = s.length;
    if (check(s, l))
        document.write("YES");
    else
        document.write("NO");
        
</script>

YES

Complejidad temporal: O(N) 
Espacio auxiliar: O(1) 
Nota : si se mencionó la longitud de una subsecuencia similar, entonces el enfoque para resolver el problema también será diferente. El enfoque para verificar si una string contiene dos subsecuencias repetidas de dos o más longitudes se analiza en esta publicación.