Find whether X exists in Y after jumbling X | Javascript 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
var MAX = 26 ; function areEqual ( a , b ) { for ( var i = 0 ; i < MAX ; i ++ ) if ( a [ i ] != b [ i ] ) return false ; return true ; } function xExistsInY ( x , y ) { if ( x . length > y . length ) return false ; var cnt_x = Array ( MAX ) . fill ( 0 ) ; var cnt = Array ( MAX ) . fill ( 0 ) ; for ( var i = 0 ; i < x . length ; i ++ ) cnt_x [ x [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] ++ ; for ( var i = 0 ; i < x . length ; i ++ ) cnt [ y [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] ++ ; if ( areEqual ( cnt_x , cnt ) ) return true ; for ( var i = 1 ; i < y . length - x . length + 1 ; i ++ ) { cnt [ y [ i - 1 ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] -- ; cnt [ y [ i + x . length - 1 ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] ++ ; if ( areEqual ( cnt , cnt_x ) ) return true ; } return false ; } var x = " " ; var y = " " ; if ( xExistsInY ( x , y ) ) document . write ( " " ) ; else document . write ( " " ) ;