leetcode 395. 至少有 K 个重复字符的最长子串

叁歲伎倆 2022-09-03 12:16 83阅读 0赞

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1：

输入：s = "aaabb", k = 3  
输出：3  
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。  
示例 2：

输入：s = "ababbc", k = 2  
输出：5  
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

题意回顾  
给你字符串 s，所谓合法子串 T：T中的每个字符的出现次数都不小于 k。求出 T 子串的最长长度。

思路展开  
先整体考虑，如果某个字符在整个字符串中的出现次数 < k，那它一定不会出现在合法子串中。  
s: aaabbaa,k: 3，b 只出现 2 次，它肯定不会出现在合法子串中，要到它的两侧找。  
考察aaa和aa，变成一个规模较小的子问题，递归去求aaa和aa中合法子串的最长长度。  
当递归到子问题的规模足够小，即，子串的长度小于 k，即便子串的字符都相同，字符的出现次数也小于 k，所以没有合法子串，返回 0  
充分剪枝  
当子串的长度小于 k 就返回 0，结束递归，而不是用「不再构成区间（start > end）」作为递归的出口，即提前回溯，不做不必要的搜索。  
如果当前递归的子串的两端，即 start 和 end 上的字符，在当前子串中出现的次数小于 k，则合法子串肯定不包含，移动指针，直到指向不小于k的字符。有些状态直接不考察，也是在剪枝。

#define MAX(a, b) (a) > (b) ? (a) : (b)
    int LongestSubString(char *s, int start, int end, int k)
    {
        if ((start >= end) || ((end - start) < k)) { // 区间的长度小于k，不存在满足条件的T串
            return 0;
        }
    
        int array[26];
        memset(array, 0, sizeof(array));
        for (int i = start; i < end; i++) { // 统计当前区间的字符的出现次数
            array[s[i] - 'a']++;
        }
        // 在区间长度>=k的前提下，如果start位置上的字符出现的次数小于k
        while ((end - start >= k) && (array[s[start] - 'a'] < k)) {
            start++; // 则T子串肯定不包含这个start字符，start指针右移
        }
        // 在区间长度>=k的前提下，如果end位置上的字符出现的次数小于k
        while ((end - start >= k) && (array[s[end - 1] - 'a'] < k)) {
            end--; // 则T子串肯定不包含这个end字符，end指针左移
        }
    
        int sepratePos = -1;
        for (int i = start; i < end; i++) {
            if (array[s[i] - 'a'] < k) { // 如果区间长度因此而 < k，直接返回0
                sepratePos = i;
                break;
            }
        }
        if (sepratePos == -1) {
            return end - start;
        }
    
        int result = LongestSubString(s, start, sepratePos, k);
        if (result > (end - sepratePos - 1)) {
            return result;
        }
        result = MAX(result, LongestSubString(s, sepratePos + 1, end, k));
    
        return result;
    }
    
    int longestSubstring(char * s, int k){
        int len = strlen(s);
        if (k == 1) {
            return len;
        }
        if (len < k) {
            return 0;
        }
    
        return LongestSubString(s, 0, strlen(s), k);
    }