Encuentra si X existe en Y después de mezclar X

Dadas dos strings X e Y que contienen alfabetos en minúsculas, la tarea es verificar si existe alguna permutación de la string X en Y como su substring.

Ejemplos: 

Entrada: X = «skege», Y = «geeksforgeeks» 
Salida: Sí  ,
«geeks» es una permutación de X que 
aparece como una substring en Y.

Entrada: X = “aabb”, Y = “bbbbbbb” 
Salida: No  

Enfoque: Este problema se puede resolver utilizando la técnica de dos punteros .

• Calcule el conteo de frecuencia de cada carácter de la string X y guárdelo en una array, digamos cnt_X[] .
• Ahora, para la substring Y[i…(i+X.length()-1)] , se puede generar la misma array de frecuencia, digamos cnt[] .
• Usando la array del paso 2, el conteo de frecuencia para la siguiente ventana se puede calcular en tiempo O(1) al disminuir cnt[Y[i] – ‘a’] en 1 e incrementar cnt[Y[i + X.length( )] – ‘a’] por 1 .
• Compare cnt[] y cnt_X[] para cada ventana. Si ambos son iguales, se ha encontrado una coincidencia.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 26;
 
// Function that returns true if both
// the arrays have equal values
bool areEqual(int* a, int* b)
{
    // Test the equality
    for (int i = 0; i < MAX; i++)
        if (a[i] != b[i])
            return false;
    return true;
}
 
// Function that returns true if any permutation
// of X exists as a substring in Y
bool xExistsInY(string x, string y)
{
 
    // Base case
    if (x.size() > y.size())
        return false;
 
    // To store cumulative frequency
    int cnt_x[MAX] = { 0 };
    int cnt[MAX] = { 0 };
 
    // Finding the frequency of
    // characters in X
    for (int i = 0; i < x.size(); i++)
        cnt_x[x[i] - 'a']++;
 
    // Finding the frequency of characters
    // in Y upto the length of X
    for (int i = 0; i < x.size(); i++)
        cnt[y[i] - 'a']++;
 
    // Equality check
    if (areEqual(cnt_x, cnt))
        return true;
 
    // Two pointer approach to generate the
    // entire cumulative frequency
    for (int i = 1; i < y.size() - x.size() + 1; i++) {
 
        // Remove the first character of
        // the previous window
        cnt[y[i - 1] - 'a']--;
 
        // Add the last character of
        // the current window
        cnt[y[i + x.size() - 1] - 'a']++;
 
        // Equality check
        if (areEqual(cnt, cnt_x))
            return true;
    }
 
    return false;
}
 
// Driver code
int main()
{
    string x = "skege";
    string y = "geeksforgeeks";
 
    if (xExistsInY(x, y))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
class GFG
{
static int MAX = 26;
 
// Function that returns true if both
// the arrays have equal values
static boolean areEqual(int []a, int []b)
{
    // Test the equality
    for (int i = 0; i < MAX; i++)
        if (a[i] != b[i])
            return false;
    return true;
}
 
// Function that returns true if
// any permutation of X exists
// as a subString in Y
static boolean xExistsInY(String x, String y)
{
 
    // Base case
    if (x.length() > y.length())
        return false;
 
    // To store cumulative frequency
    int []cnt_x = new int[MAX];
    int []cnt = new int[MAX];
 
    // Finding the frequency of
    // characters in X
    for (int i = 0; i < x.length(); i++)
        cnt_x[x.charAt(i) - 'a']++;
 
    // Finding the frequency of characters
    // in Y upto the length of X
    for (int i = 0; i < x.length(); i++)
        cnt[y.charAt(i) - 'a']++;
 
    // Equality check
    if (areEqual(cnt_x, cnt))
        return true;
 
    // Two pointer approach to generate the
    // entire cumulative frequency
    for (int i = 1; i < y.length() -
                        x.length() + 1; i++)
    {
 
        // Remove the first character of
        // the previous window
        cnt[y.charAt(i - 1) - 'a']--;
 
        // Add the last character of
        // the current window
        cnt[y.charAt(i + x.length() - 1) - 'a']++;
 
        // Equality check
        if (areEqual(cnt, cnt_x))
            return true;
    }
    return false;
}
 
// Driver code
public static void main(String[] args)
{
    String x = "skege";
    String y = "geeksforgeeks";
 
    if (xExistsInY(x, y))
        System.out.print("Yes");
    else
        System.out.print("No");
}
}
 
// This code contributed by PrinciRaj1992

# Python3 implementation of the approach
MAX = 26
 
# Function that returns true if both
# the arrays have equal values
def areEqual(a, b):
     
    # Test the equality
    for i in range(MAX):
        if (a[i] != b[i]):
            return False
    return True
 
# Function that returns true if any permutation
# of X exists as a sub in Y
def xExistsInY(x,y):
 
    # Base case
    if (len(x) > len(y)):
        return False
 
    # To store cumulative frequency
    cnt_x = [0] * MAX
    cnt = [0] * MAX
 
    # Finding the frequency of
    # characters in X
    for i in range(len(x)):
        cnt_x[ord(x[i]) - ord('a')] += 1;
 
    # Finding the frequency of characters
    # in Y upto the length of X
    for i in range(len(x)):
        cnt[ord(y[i]) - ord('a')] += 1
 
    # Equality check
    if (areEqual(cnt_x, cnt)):
        return True
 
    # Two pointer approach to generate the
    # entire cumulative frequency
    for i in range(1, len(y) - len(x) + 1):
 
        # Remove the first character of
        # the previous window
        cnt[ord(y[i - 1]) - ord('a')] -= 1
 
        # Add the last character of
        # the current window
        cnt[ord(y[i + len(x) - 1]) - ord('a')] += 1
 
        # Equality check
        if (areEqual(cnt, cnt_x)):
            return True
 
    return False
 
# Driver Code
if __name__ == '__main__':
    x = "skege"
    y = "geeksforgeeks"
 
    if (xExistsInY(x, y)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
static int MAX = 26;
 
// Function that returns true if both
// the arrays have equal values
static bool areEqual(int []a,
                     int []b)
{
    // Test the equality
    for (int i = 0; i < MAX; i++)
        if (a[i] != b[i])
            return false;
    return true;
}
 
// Function that returns true if
// any permutation of X exists
// as a subString in Y
static bool xExistsInY(String x,
                       String y)
{
 
    // Base case
    if (x.Length > y.Length)
        return false;
 
    // To store cumulative frequency
    int []cnt_x = new int[MAX];
    int []cnt = new int[MAX];
 
    // Finding the frequency of
    // characters in X
    for (int i = 0; i < x.Length; i++)
        cnt_x[x[i] - 'a']++;
 
    // Finding the frequency of characters
    // in Y upto the length of X
    for (int i = 0; i < x.Length; i++)
        cnt[y[i] - 'a']++;
 
    // Equality check
    if (areEqual(cnt_x, cnt))
        return true;
 
    // Two pointer approach to generate the
    // entire cumulative frequency
    for (int i = 1; i < y.Length -
                        x.Length + 1; i++)
    {
 
        // Remove the first character of
        // the previous window
        cnt[y[i - 1] - 'a']--;
 
        // Add the last character of
        // the current window
        cnt[y[i + x.Length - 1] - 'a']++;
 
        // Equality check
        if (areEqual(cnt, cnt_x))
            return true;
    }
    return false;
}
 
// Driver code
public static void Main(String[] args)
{
    String x = "skege";
    String y = "geeksforgeeks";
 
    if (xExistsInY(x, y))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation of the approach
 
var MAX = 26;
 
// Function that returns true if both
// the arrays have equal values
function areEqual(a, b)
{
    // Test the equality
    for (var i = 0; i < MAX; i++)
        if (a[i] != b[i])
            return false;
    return true;
}
 
// Function that returns true if any permutation
// of X exists as a substring in Y
function xExistsInY(x, y)
{
 
    // Base case
    if (x.length > y.length)
        return false;
 
    // To store cumulative frequency
    var cnt_x = Array(MAX).fill(0);
    var cnt = Array(MAX).fill(0);
 
    // Finding the frequency of
    // characters in X
    for (var i = 0; i < x.length; i++)
        cnt_x[x[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
 
    // Finding the frequency of characters
    // in Y upto the length of X
    for (var i = 0; i < x.length; i++)
        cnt[y[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
 
    // Equality check
    if (areEqual(cnt_x, cnt))
        return true;
 
    // Two pointer approach to generate the
    // entire cumulative frequency
    for (var i = 1; i < y.length - x.length + 1; i++) {
 
        // Remove the first character of
        // the previous window
        cnt[y[i - 1].charCodeAt(0) - 'a'.charCodeAt(0)]--;
 
        // Add the last character of
        // the current window
        cnt[y[i + x.length - 1].charCodeAt(0) - 'a'.charCodeAt(0)]++;
 
        // Equality check
        if (areEqual(cnt, cnt_x))
            return true;
    }
 
    return false;
}
 
// Driver code
var x = "skege";
var y = "geeksforgeeks";
if (xExistsInY(x, y))
    document.write( "Yes");
else
    document.write("No");
 
</script>

Yes

Complejidad de tiempo: O(xLen + yLen) donde xLen y yLen son las longitudes de las strings X e Y respectivamente.