題目

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

題解

參考：官方題解 Approach 2: Divide And Conquer

分而治之的思想，提示：每次用不符合條件的字母作為樞軸，將 s 劃分為左右兩個子問題。

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;} }

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的leetcode 395. Longest Substring with At Least K Repeating Characters| 395. 至少有 K 个重复字符的最长子串（分治法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。