java - 使用分而治之的方法背后的推理

Question

我正在尝试解决 this question在 LeetCode 上:

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.
Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.
For s = "YazaAay", the expected output is: "aAa"

top voted solutions其中之一使用分而治之的方法:

class Solution {
    public String longestNiceSubstring(String s) {
        if (s.length() < 2) return "";
        char[] arr = s.toCharArray();
        Set<Character> set = new HashSet<>();
        for (char c: arr) set.add(c);
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if (set.contains(Character.toUpperCase(c)) && set.contains(Character.toLowerCase(c))) continue;
            String sub1 = longestNiceSubstring(s.substring(0, i));
            String sub2 = longestNiceSubstring(s.substring(i+1));
            return sub1.length() >= sub2.length() ? sub1 : sub2;
        }
        return s; 
    }
}

我了解它是如何工作的，但不了解使用分而治之的方法背后的直觉。换句话说，如果我在忘记它的所有内容后几天/几周再次重新审视该问题，我将无法意识到这是一个分而治之的问题。
是什么“东西”使它可以通过分而治之的方法解决？

Answer 1

这就是算法可以用简单的英语描述的方式:
如果整个字符串都很好，我们就完成了。
否则，必须存在仅在一种情况下存在的字符。这样的字符自然地将字符串分成两个子字符串。分别征服它们中的每一个，并比较结果。
编辑:顺便说一句，我认为这不是 D&C 问题的一个很好的例子。关键是，一旦我们遇到第一个“坏”字符，它左边的子串就很好。没有必要深入其中。只需记录它的长度并继续。这是一个简单的循环。