public String longestPalindrome_3(String s){// greedy solution
        String res = "";
        for(int i = 0; i < s.length(); ++i){
            String ex = extend(s, i, i);
            res = res.length() < ex.length() ? ex : res;
        }
        for(int i = 0; i < s.length() - 1; ++i){
            String ex = extend(s, i, i+1);
            res = res.length() < ex.length() ? ex : res;
        }
        return res;
    }