find_max_subArray.py

"""
Given an array: ['A', 'B', 'C', 'D', 'F', 'D']
find maximum subarray which contain one unique char. You are allowd to change at most K chars to any other char
"""
import collections

def findMax(Array, K):
    if not Array:
        return 0

    res = 0
    majorifytCount = 0
    left = 0
    count = collections.Counter()

    for right in range(len(Array)):
        count[Array[right]] += 1

        if count[Array[right]] > majorifytCount:
            majorifytCount = count[Array[right]]

        if right - left + 1 - majorifytCount <= K:
            res = max(res, right - left + 1)
        else:
            count[Array[left]] -= 1
            left += 1

    return res

if __name__ == "__main__":
    print()
    A = ['C', 'D', 'C', 'D', 'F', 'D', 'D', 'E', 'D', 'E', 'D']
    K = 3
    print(findMax(A, K))