1. 題目

找到給定字符串（由小寫字符組成）中的最長(zhǎng)子串 T ， 要求 T 中的每一字符出現(xiàn)次數(shù)都不少于 k 。輸出 T 的長(zhǎng)度。

示例 1: 輸入: s = "aaabb", k = 3 輸出: 3 最長(zhǎng)子串為 "aaa" ，其中 'a' 重復(fù)了 3 次。示例 2: 輸入: s = "ababbc", k = 2 輸出: 5 最長(zhǎng)子串為 "ababb" ，其中 'a' 重復(fù)了 2 次， 'b' 重復(fù)了 3 次。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 找出字符串中次數(shù)小于 k 的，他們不能出現(xiàn)在答案中
• 以他們的位置把字符串切開，遞歸求解子問(wèn)題
• 當(dāng)一個(gè)子串中，字符計(jì)數(shù)都>= k 時(shí)，更新最大長(zhǎng)度
• 剪枝，當(dāng)前處理的字符串長(zhǎng)度 <= 最大長(zhǎng)度時(shí)，不再遞歸處理

class Solution {int maxlen = 0; public:int longestSubstring(string s, int k) {if(s.size() <= maxlen)//剪枝return 0;int count[26] = {0}, i, left = 0;for(i = 0; i < s.size(); ++i)count[s[i]-'a']++;vector<int> split;for(i = 0; i < s.size(); ++i){if(count[s[i]-'a'] > 0 && count[s[i]-'a'] < k)split.push_back(i);//不能出現(xiàn)的字符位置}if(split.empty())maxlen = max(maxlen, int(s.size()));//沒(méi)有切分位置，滿足題意for(i = 0; i < split.size(); ++i){longestSubstring(s.substr(left, split[i]-left), k);left = split[i]+1;if(i == split.size()-1 && left < s.size())longestSubstring(s.substr(left, s.size()-left), k);}return maxlen;} };

8 ms 6.8 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 395. 至少有K个重复字符的最长子串（分治）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。