Longest equal substring with cost less than K | Function to find the maximum length ; Fill the prefix array with the difference of letters ; Update the maximum length ; Driver code
def solve ( X , Y , N , K ) : NEW_LINE INDENT count = [ 0 ] * ( N + 1 ) ; NEW_LINE sol = 0 ; NEW_LINE count [ 0 ] = 0 ; NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT count [ i ] = ( count [ i - 1 ] + abs ( ord ( X [ i - 1 ] ) - ord ( Y [ i - 1 ] ) ) ) ; NEW_LINE DEDENT j = 0 ; NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT while ( ( count [ i ] - count [ j ] ) > K ) : NEW_LINE INDENT j += 1 ; NEW_LINE DEDENT sol = max ( sol , i - j ) ; NEW_LINE DEDENT return sol ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 4 ; NEW_LINE X = " abcd " ; NEW_LINE Y = " bcde " ; NEW_LINE K = 3 ; NEW_LINE print ( solve ( X , Y , N , K ) ) ; NEW_LINE DEDENT