LeetCode:395. Longest Substring with At Least K Repeating Characters至少有K个重复字符的最长子串(C语言)

- 日理万妓 2022-12-09 02:35 80阅读 0赞

**题目描述：**  
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

示例 1:

输入:  
s = “aaabb”, k = 3

输出:  
3

最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。

示例 2:

输入:  
s = “ababbc”, k = 2

输出:  
5

最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

void recursion(char *s, int left, int right, int k, int* pret){ 
        if(right - left + 1 <= *pret){ 
            return;
        }
    
        if(k > right - left + 1){ 
            return;
        }
    
        if(k < 2){ 
            if(right - left + 1 > *pret){ 
                *pret = right - left + 1;
            }
        }
    
        //哈希表初始化
        int hash[26] = { 0};
        for(int i = left;i <= right;i++){ 
            hash[s[i] - 'a']++;
        }
    
        //分割递归
        for(int i = left;i <= right;i++){ 
            //若该子串中给有某个字符出现次数小于k次
            if(hash[s[i] - 'a'] < k){ 
                recursion(s, left, i - 1, k, pret);
                recursion(s, i + 1, right, k, pret);
                return;
            }
        }
    
        //若该子串中所有字符出现次数均大于k次
        *pret = right - left + 1;
    
    }
    
    int longestSubstring(char * s, int k){ 
        int ret = 0;
        recursion(s, 0, strlen(s) - 1, k, &ret);
        return ret;
    }

**运行结果：**  
![在这里插入图片描述][20200921145521861.png_pic_center]  
**Notes:**  
参考[https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/c-di-gui-by-yyy-108-2/][https_leetcode-cn.com_problems_longest-substring-with-at-least-k-repeating-characters_solution_c-di-gui-by-yyy-108-2]

[20200921145521861.png_pic_center]: /images/20221123/0e275d13e87f4fc7b1236fbbce0485cf.png
[https_leetcode-cn.com_problems_longest-substring-with-at-least-k-repeating-characters_solution_c-di-gui-by-yyy-108-2]: https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/c-di-gui-by-yyy-108-2/