当前位置：首页 > article >正文

每日一题|2516. 每种字符至少取 K 个|双指针、最长子串、字典

article 2024/9/29 11:41:02

本题需要转化求解目标。

对于一个序列，两头收集的最少数量的时候，剩下的部分（我们称之为子串）就会对应的越长。也就是说，我们只要求解一个满足要求的最长子串，使得两边剩余的字符数量刚好满足要求。

由于题目需要分别记录固定字符的个数，采用字典进行计算。

1.初始化

初始化包含字典、结果值。

首先遍历字符串的全部字符，统计在字典里，也就是子串长度为0。

        cnt_dict = {'a':0, 'b':0, 'c':0}
        ans = len(s)

        for ch in s:
            cnt_dict[ch] += 1
        
        if min(cnt_dict.values()) >= k:
            ans = len(s)
        else:
            return -1

这里需要做一个剪枝操作：如果统计的全部个数当中存在一个字符出现的个数小于要求，则可以直接返回-1。其余的情况，ans不变。

2.双指针遍历

两个指针left，right，都同时从左侧出发，先移动right，在right固定的时候，逐渐收紧left，直到刚好存在一个字符的数量等于k。

所以是两层循环，外层for循环移动right指针，内层的while循环收紧left指针。

每移动一次right指针，所指元素的数量就要-1（子串的长度在变长），每移动一次left指针，所指元素的数量+1（子串在变短）。

        l = 0
        for r, ch in enumerate(s):
            cnt_dict[ch] -= 1
            while l < r and min(cnt_dict.values()) < k:
                cnt_dict[s[l]] += 1
                l += 1
            if min(cnt_dict.values()) >= k:
                ans = min(ans, len(s) - (r - l + 1))

最后，如果在某一个时刻，所有的数量的最小值达到要求，则更新ans的值为当前“子串外字符长度”和上一次的ans的最小值。