Find whether X exists in Y after jumbling X | Python3 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 sub 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
MAX = 26 NEW_LINE def areEqual ( a , b ) : NEW_LINE INDENT for i in range ( MAX ) : NEW_LINE INDENT if ( a [ i ] != b [ i ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def xExistsInY ( x , y ) : NEW_LINE INDENT if ( len ( x ) > len ( y ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT cnt_x = [ 0 ] * MAX NEW_LINE cnt = [ 0 ] * MAX NEW_LINE for i in range ( len ( x ) ) : NEW_LINE INDENT cnt_x [ ord ( x [ i ] ) - ord ( ' a ' ) ] += 1 ; NEW_LINE DEDENT for i in range ( len ( x ) ) : NEW_LINE INDENT cnt [ ord ( y [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT if ( areEqual ( cnt_x , cnt ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( 1 , len ( y ) - len ( x ) + 1 ) : NEW_LINE INDENT cnt [ ord ( y [ i - 1 ] ) - ord ( ' a ' ) ] -= 1 NEW_LINE cnt [ ord ( y [ i + len ( x ) - 1 ] ) - ord ( ' a ' ) ] += 1 NEW_LINE if ( areEqual ( cnt , cnt_x ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT x = " skege " NEW_LINE y = " geeksforgeeks " NEW_LINE if ( xExistsInY ( x , y ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT