Longest equal substring with cost less than K | Java 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
class GFG { static int solve ( String X , String Y , int N , int K ) { int [ ] count = new int [ N + 1 ] ; int sol = 0 ; count [ 0 ] = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { count [ i ] = count [ i - 1 ] + Math . abs ( X . charAt ( i - 1 ) - Y . charAt ( i - 1 ) ) ; } int j = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { while ( ( count [ i ] - count [ j ] ) > K ) { j ++ ; } sol = Math . max ( sol , i - j ) ; } return sol ; } public static void main ( String [ ] args ) { int N = 4 ; String X = " abcd " , Y = " bcde " ; int K = 3 ; System . out . print ( solve ( X , Y , N , K ) + "NEW_LINE"); } }