Maximum length substring having all same characters after k changes | function to find the maximum length of substring having character ch ; traverse the whole string ; if character is not same as ch increase count ; While count > k traverse the string again until count becomes less than k and decrease the count when characters are not same ; length of substring will be rightIndex - leftIndex + 1. Compare this with the maximum length and return maximum length ; function which returns maximum length of substring ; Driver Code
def findLen ( A , n , k , ch ) : NEW_LINE INDENT maxlen = 1 NEW_LINE cnt = 0 NEW_LINE l = 0 NEW_LINE r = 0 NEW_LINE while r < n : NEW_LINE INDENT if A [ r ] != ch : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT while cnt > k : NEW_LINE INDENT if A [ l ] != ch : NEW_LINE INDENT cnt -= 1 NEW_LINE DEDENT l += 1 NEW_LINE DEDENT maxlen = max ( maxlen , r - l + 1 ) NEW_LINE r += 1 NEW_LINE DEDENT return maxlen NEW_LINE DEDENT def answer ( A , n , k ) : NEW_LINE INDENT maxlen = 1 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT maxlen = max ( maxlen , findLen ( A , n , k , chr ( i + ord ( ' A ' ) ) ) ) NEW_LINE maxlen = max ( maxlen , findLen ( A , n , k , chr ( i + ord ( ' a ' ) ) ) ) NEW_LINE DEDENT return maxlen NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE k = 2 NEW_LINE A = " ABABA " NEW_LINE print ( " Maximum ▁ length ▁ = " , answer ( A , n , k ) ) NEW_LINE n = 6 NEW_LINE k = 4 NEW_LINE B = " HHHHHH " NEW_LINE print ( " Maximum ▁ length ▁ = " , answer ( B , n , k ) ) NEW_LINE DEDENT