題目
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
解題之法
class Solution {
public:
int longestSubstring(string s, int k) {
int res = 0, i = 0, n = s.size();
while (i + k <= n) {
int m[26] = {0}, mask = 0, max_idx = i;
for (int j = i; j < n; ++j) {
int t = s[j] - 'a';
++m[t];
if (m[t] < k) mask |= (1 << t);
else mask &= (~(1 << t));
if (mask == 0) {
res = max(res, j - i + 1);
max_idx = j;
}
}
i = max_idx + 1;
}
return res;
}
};
分析
這道題給了我們一個字符串s和一個正整數(shù)k，讓我們求一個最大子字符串并且每個字符必須至少出現(xiàn)k次。難點在于如何快速的判斷某一個字符串是否所有的元素都已經(jīng)滿足了至少出現(xiàn)k次這個條件册倒，雖然用哈希表建立了字符和其出現(xiàn)次數(shù)之間的映射，但是如果每一次都要遍歷哈希表中的所有字符看其出現(xiàn)次數(shù)是否大于k思犁，未免有些不高效。
而用mask就很好的解決了這個問題进肯，由于字母只有26個激蹲，而整型mask有32位，足夠用了江掩，每一位代表一個字母学辱，如果為1，表示該字母不夠k次环形，如果為0就表示已經(jīng)出現(xiàn)了k次策泣，這種思路真是太聰明了。
我們遍歷字符串抬吟，對于每一個字符萨咕，我們都將其視為起點，然后遍歷到末尾火本，我們增加哈希表中字母的出現(xiàn)次數(shù)危队，如果其小于k，我們將mask的對應位改為1钙畔，如果大于等于k茫陆，將mask對應位改為0。然后看mask是否為0擎析，是的話就更新res結(jié)果簿盅，然后把當前滿足要求的子字符串的起始位置j保存到max_idx中，等內(nèi)層循環(huán)結(jié)束后叔锐，將外層循環(huán)變量i賦值為max_idx+1挪鹏，繼續(xù)循環(huán)直至結(jié)束。
