# 1763. Longest Nice Substring
###### tags: `Leetcode` `Easy` `Divide and Conquer`
Link: https://leetcode.com/problems/longest-nice-substring/
## 思路 $O(N^2)$ $O(N)$
用divide And Conquer的[原因](https://leetcode.com/problems/longest-nice-substring/discuss/1645774/Java-or-Why-Divide-and-Conquer-Explained)(链接里面的前三点) 如果有一个字母的大写或者小写在当下字符串里面不存在 那么这个string的任何substring都不会是nice string 所以最好的方法是直接去掉它

所有divide and conquer的题目都先想象一个树形结构
第一层先检验1个长度为N(N=s.length())的字串是否满足条件
第二层检验两个
第三层检验四个 以此类推
划分条件是如果碰到一个字母它的大写和小写不在当前字串里面同时存在，就分开
## Code
java

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

c++

class Solution {
public:
    string longestNiceSubstring(string s) {
        if(s.length()<2) return "";
        set<char> set;
        for(int i=0; i<s.length(); i++){
            set.insert(s[i]);
        }
        for(int i=0; i<s.length(); i++){
            if(set.find(tolower(s[i]))==set.end() || set.find(toupper(s[i]))==set.end()){
                string s1 = longestNiceSubstring(s.substr(0,i));
                string s2 = longestNiceSubstring(s.substr(i+1));
                return s1.length()>=s2.length()?s1:s2;
            }
        }
        return s;
    }
};