题解 | #牛牛的AC#

解题思路，将字符串转换为0， 1 数组。原题求解等价于“序列的连续和小于等k，的最长的长度”

1. 采用双指针进行遍历，
2. 特殊情况 k=0, 采用动态规划，动态转移方程如下：
   dp[i] = dp[i-1] + 1 (arr[i] == 0)
   dp[i] = 0 (arr[i] == 1)

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param k int整型 
# @param s string字符串 
# @return int整型
#
class Solution:
    def _transform(self, s, ch_key):
        """ 转化为二进制数字 """
        arr = list()
        for ch in s:
            if ch == ch_key:
                arr.append(1)
            else:
                arr.append(0)
        return arr

    def _dp_arr(self, k, arr):
        """ 双指针求解 """
        # 边界条件处理
        if sum(arr) <= k:
            return len(arr)

        if k == 0:
            # 以dp[i]为结尾的，0的最大长度
            dp = [0 for i in range(len(arr))]
            if arr[0] == 0:
                dp[0] = 1
            for i in range(1, len(arr)):
                if arr[i] == 0:
                    dp[i] = dp[i-1] + 1
                else:
                    dp[i] = 0
            return max(dp)


        # 找到右边终点， 双指针移动，保证指针之间和为k，保存最长的长度
        max_len = 0
        start_i, end_i, sum_tmp = 0, 0, 0
        for i in range(len(arr)):
            sum_tmp += arr[i]
            if sum_tmp <= k:
                end_i = i
                max_len = i + 1
            elif sum_tmp > k:
                break

        # 开始双指针移动
        for j in range(end_i+1, len(arr)):
            if arr[j] == 1:
                for i in range(start_i, j):
                    if arr[i] == 1:
                        start_i = i + 1
                        max_len = max(max_len, j - start_i + 1)
                        break
                        break
        return max_len
    def Solve(self , k , s ):
        # write code here
        max_len = 0
        for ch in list("AC"):
            arr = self._transform(s, ch)
            max_len = max(max_len, self._dp_arr(k, arr))


        return max_len