Longest Nice Substring

给一个string, 定义nice是string的substring, 并且每个字符都有对应大小写的字符. 求最长nice substring.

这个题微软面试经常考啊, 帮人写过好几次了, 这题主要的陷阱就是看似能用滑窗扫描, 其实不能, 原因是nice的substring没有包含的关系, 所以最简单的做法就是2个for循环找所有可能的情况, 然后还有一种做法是, 先预处理string, 然后把不可能组成nice string的字符, 整个string都没有出现大小写的字符, 放到set里, 然后因为题意, 我们知道这些字符可以看做一个个split points. 也就是说我们的答案的substring肯定不会包含这些字符, 于是用一个循环找写着字符, 不断的剔去他们. 就可以找到答案了. 我看讨论区说这是什么分治法, 我觉得并不是. 只是简单的分割问题, 没有merge.

class Solution {
    public String longestNiceSubstring(String s) {
        Set<Character> set = new HashSet<>();
        for(char c : s.toCharArray()){ // all chars to set
            set.add(c);
        }
        for(int i = 0; i < 26; i++) { // find the split points
            char c = (char) ('a' + i);
            if(set.contains(c) && set.contains(Character.toUpperCase(c))){
                set.remove(c);
                set.remove(Character.toUpperCase(c));
            }
        }
        if(set.size() == 0)
            return s; // all meet the requirements
        for(int i = 0; i < s.length(); i++) {
            if(set.contains(s.charAt(i))){ 
                String left = longestNiceSubstring(s.substring(0, i));
                String right = longestNiceSubstring(s.substring(i + 1, s.length()));
                if(left.length() >= right.length())
                    return left;
                else
                    return right;
            }
        }
        return "";
    }
}