Longest equal substring with cost less than K | C ++ program to find the maximum length of equal substring within a given cost ; Function to find the maximum length ; Fill the prefix array with the difference of letters ; Update the maximum length ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int solve ( string X , string Y , int N , int K ) { int count [ N + 1 ] = { 0 } ; int sol = 0 ; count [ 0 ] = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { count [ i ] = count [ i - 1 ] + abs ( X [ i - 1 ] - Y [ i - 1 ] ) ; } int j = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { while ( ( count [ i ] - count [ j ] ) > K ) { j ++ ; } sol = max ( sol , i - j ) ; } return sol ; } int main ( ) { int N = 4 ; string X = " abcd " , Y = " bcde " ; int K = 3 ; cout << solve ( X , Y , N , K ) << " STRNEWLINE " ; return 0 ; }