> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/divide-and-conquer.md).

# Divide & Conquer

## 经典题目

[*23 Merge k Sorted Lists*](https://leetcode.com/problems/merge-k-sorted-lists/description/)

Divide the input into the minimal parts which can not be divided anymore. Then merge the adjacent two lists and return the merged lists. Keep merging until we have only one list.

```java
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return mergeKLists(lists, 0, lists.length - 1);
}
private ListNode mergeKLists(ListNode[] lists, int left, int right) {
    if (left == right) return lists[left];
    int mid = left + (right - left) / 2;
    ListNode a = mergeKLists(lists, left, mid);
    ListNode b = mergeKLists(lists, mid + 1, right);
    return merge(a, b);
}
private ListNode merge(ListNode a, ListNode b) {
    if (a == null) return b;
    if (b == null) return a;
    ListNode dummyNode = new ListNode(0);
    ListNode cur = dummyNode;
    while (a != null && b != null) {
        if (a.val < b.val) {
            cur.next = a;
            a = a.next;
        } else {
            cur.next = b;
            b = b.next;
        }
        cur = cur.next;
    }
    if (a != null) cur.next = a;
    if (b != null) cur.next = b;
    return dummyNode.next;
}
```

[*395 Longest Substring with At Least K Repeating Characters*](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/)

先扫一遍，找到freq < k的char，然后分成左右两边找，返回较大的那个。

helper function返回的是当前区间最长的substring with at least K repeating chars

{% tabs %}
{% tab title="Iterative" %}

```java
public int longestSubstring(String s, int k) {
    int ans = 0;
    for (int target = 1; target <= 26; target++) {
        int[] count = new int[26];
        int i = 0, j = 0;
        int unique = 0, noLessK = 0;
        
        while (j < s.length()) {
            if (unique <= target) {
                int index = s.charAt(j) - 'a';
                if (count[index] == 0) {
                    unique++;
                }
                count[index]++;
                if (count[index] == k) {
                    noLessK++;
                }
                j++;
            } else {
                int index = s.charAt(i) - 'a';
                if (count[index] == 1) {
                    unique--;
                }
                count[index]--;
                if (count[index] == k - 1) {
                    noLessK--;
                }
                i++;
            }
            if (unique == target && noLessK == unique) {
                ans = Math.max(ans, j - i);
            }
        }
    }
    return ans;
}
```

{% endtab %}

{% tab title="Recursion" %}

```java
public int longestSubstring(String s, int k) {
    char[] str = s.toCharArray();
    return helper(str,0,s.length(),k);
}
private int helper(char[] str, int start, int end, int k){
    if (end - start < k) return 0;//substring length shorter than k.
    int[] count = new int [26];
    for (int i = start; i<end; i++) {
        int idx = str[i] - 'a';
        count[idx]++;
    }
    for (int i=0; i<26; i++) {
        if (count[i] < k && count[i] > 0) { //count[i]=0 => i+'a' does not exist in the string, skip it.
            for (int j = start; j<end; j++) {
                if (str[j] == i+'a') {
                    int left = helper(str, start, j, k);
                    int right = helper(str, j+1, end, k);
                    return Math.max(left, right);
                }
            }
        }
    }
    return end - start;
}
```

{% endtab %}
{% endtabs %}