395.至少每个字符都重复k次的最长子串

思路：先遍历字符串，用char型数组代替hash，找到不满足条件的字符。这些字符将长字符串切割为了一个个的子串。问题就变为了再对每个子串求同样的问题。 class Solution { public: int longestSubstring(string s, int k) { if(s.size() < k) return 0; int ans = 0; int tmp = 0; // 记录有多少字符数小于k的 int char_map[128] = {0}; string word = ""; for(int i = 0; i < s.size(); i++) { char_map[s[i]]++; } for(int i = 0; i < s.size(); i++) { if(char_map[s[i]]>=k) { word += s[i]; tmp++; } else if(char_map[s[i]]>=k){ for(int j = 0; j < word.size(); j++) { char_map[word[j]]--; } tmp = longestSubstring(word, k); word = ""; if(ans<tmp) { ans = tmp; } tmp = 0; }

    }
    if(ans<tmp) {
        ans = tmp;
    }
    return ans;
}

};

作者：FFIDEAL 链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/0395-hash_map-di-gui-fen-zhi-by-ffideal-6278/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

补充一个前缀和的解法。比字符hash更nb。思路nb在遍历一遍的时候，每个位置上的不同字符累积到当前位置，已经出现的总次数知道了。因此对一个指定的区间，求每个字符是否满足k次的要求很容易就可以得到，如果不满足，就再将1个区间拆分为2个区间，这样一直拆分下去。求每个区间的满足条件的值，与最大值比较即可。 int longestSubstring(char * s, int k){ int n = strlen(s), prefix[26][n+1]; memset(prefix, 0, sizeof(prefix)); // 1. 预处理前缀和：方便计算区间内数字出现个数 for (int i = 0; i < n; i++) { for (int j = 0; j < 26; j++) { prefix[j][i+1] = prefix[j][i]; } prefix[s[i]-'a'][i+1]++; } // 2. 统计区间 [start, end] 内满足 s[i] < k 进行划分区间递归 int helper(int start, int end) { for (int i = start; i <= end; i++) { if (prefix[s[i]-'a'][end+1] - prefix[s[i]-'a'][start] < k) { return fmax(helper(start, i - 1), helper(i + 1, end)); } } return fmax(end - start + 1, 0); // 证明 [start,end] 都满足或不存在区间 } return helper(0, n - 1); }

作者：boille 链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/26zi-fu-qian-zhui-he-fen-zhi-er-cha-shu-de-hou-xu-/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

zwzhome / algorithm

395.至少每个字符都重复k次的最长子串 #2