Find whether X exists in Y after jumbling X | Java 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
class GFG { static int MAX = 26 ; static boolean areEqual ( int [ ] a , int [ ] b ) { for ( int i = 0 ; i < MAX ; i ++ ) if ( a [ i ] != b [ i ] ) return false ; return true ; } static boolean xExistsInY ( String x , String y ) { if ( x . length ( ) > y . length ( ) ) return false ; int [ ] cnt_x = new int [ MAX ] ; int [ ] cnt = new int [ MAX ] ; for ( int i = 0 ; i < x . length ( ) ; i ++ ) cnt_x [ x . charAt ( i ) - ' a ' ] ++ ; for ( int i = 0 ; i < x . length ( ) ; i ++ ) cnt [ y . charAt ( i ) - ' a ' ] ++ ; if ( areEqual ( cnt_x , cnt ) ) return true ; for ( int i = 1 ; i < y . length ( ) - x . length ( ) + 1 ; i ++ ) { cnt [ y . charAt ( i - 1 ) - ' a ' ] -- ; cnt [ y . charAt ( i + x . length ( ) - 1 ) - ' a ' ] ++ ; if ( areEqual ( cnt , cnt_x ) ) return true ; } return false ; } 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 " ) ; } }