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