leetcode 395. Longest Substring with At Least K Repeating Characters| 395. 至少有 K 个重复字符的最长子串（分治法）

迈不过友情╰ 2022-09-01 09:13 110阅读 0赞

## 题目 ##

[https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/][https_leetcode.com_problems_longest-substring-with-at-least-k-repeating-characters]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

参考：官方题解 [Approach 2: Divide And Conquer][Approach 2_ Divide And Conquer]

分而治之的思想，提示：每次用不符合条件的字母作为枢轴，将 s 划分为左右两个子问题。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

class Solution { 
        public int longestSubstring(String s, int k) { 
            return partition(s, 0, s.length() - 1, k);
        }
    
        public int partition(String s, int L, int R, int k) { 
            if (L < 0 || R >= s.length() || L > R || R - L + 1 < k) return 0;
            int[] count = new int[26]; // 对应字母出现次数
            int[] index = new int[26]; // 对应字母最后一次在字符串中出现的位置
            for (int i = L; i <= R; i++) { 
                count[s.charAt(i) - 'a']++;
                index[s.charAt(i) - 'a'] = i;
            }
    
            int longest = R - L + 1;
            for (int i = 0; i < count.length; i++) { 
                if (count[i] > 0 && count[i] < k) {  // 将出现次数小于k的字母作为枢轴
                    int M = index[i];
                    return Math.max(partition(s, L, M - 1, k), partition(s, M + 1, R, k));
                }
            }
            return longest;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_longest-substring-with-at-least-k-repeating-characters]: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/5d8f0108187d46f88253b88f5224bdcd.png
[Approach 2_ Divide And Conquer]: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/4903c642fd0046f5bc171505063992fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/86b50198afe14764b0d254861d731915.png