題目要求

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 = 3Output:
3The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:Input:
s = "ababbc", k = 2Output:
5The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

找出字符串中的最長子字符串，滿足該子字符串中任何字符出現的次數都大于k。

思路和代碼

這是一個經典的分治法解決的問題，關鍵在于我們如何將這個問題分解為更小的子問題。反過來想，這個子字符串一定不包含什么元素呢？當一個元素出現的總次數小于k，那么該元素一定不在子字符串中，只需要將其作為分界點，分別找出左半部分和右半部分的滿足條件的最長子字符串。

    public int longestSubstring(String s, int k) {return longestSubstring(s, k, 0, s.length()-1);}public int longestSubstring(String s, int k, int left, int right) {if(left > right) {return 0;}int[] count = new int[26];for(int i = left ; i<=right ; i++) {count[s.charAt(i) - 'a']++;}int result = right - left + 1;for(int i = left ; i<=right ; i++) {if(count[s.charAt(i)-'a'] < k && count[s.charAt(i)-'a'] > 0) {int leftLongest = longestSubstring(s, k, left, i-1);int rightLongest = longestSubstring(s, k, i+1, right);result = Math.max(leftLongest, rightLongest);break;}}return result;}