L家挂人题：返回所有对称子集

发下我的解。去年onsite前一晚还背了此解，
当天面试5轮头晕最后一轮面这题，解法忘记了。
DFS 递归。
class Node {
    int left;
    int right;
    public Node(int left, int right){
        this.left = left;
        this.right = right;
    }
}

public class SubsequencePalindromeWayI {
       
        public static List <String> findAllPalindromicSubsequences(String input){
                List <String > res = new ArrayList <String> ();
        HashMap <Character, List<Integer>> map = new HashMap <Character, List<Integer>>();
        HashMap <Character, Node> locations = new HashMap <Character, Node>();
        char [] chs = input.toCharArray();
        for(int i=0;i<chs.length;i++){
            if(map.containsKey(chs[i])){
                map.get(chs[i]).add(i);
            }
            else{
                List <Integer> tmp = new ArrayList <Integer> ();
                tmp.add(i);
                map.put(chs[i],tmp);
            }
        }
        Set <Character> keySet = map.keySet();
        for(Character ch:keySet)locations.put(ch, new Node(0,map.get(ch).size()-1));              
        StringBuilder strb1 = new StringBuilder();
        StringBuilder strb2 = new StringBuilder();
        DFS(0,chs.length-1,strb1,strb2,keySet,map,locations,res);
        return res;                    
    }
   

    public static void DFS (int left, int right,
                             StringBuilder strb1, StringBuilder strb2, Set <Character> keySet,
                             HashMap <Character, List<Integer>> map, HashMap <Character, Node> locations,List <String> res) {
        for(Character ch:keySet){
            Node curNode=locations.get(ch);
            List <Integer> list = map.get(ch);
            int left_Copy = curNode.left;
            int right_Copy = curNode.right;
            while((curNode.left<=curNode.right)&&(list.get(curNode.left)<left)){
                    curNode.left++;
            }
            while((curNode.left<=curNode.right)&&(list.get(curNode.right)>right)){
                    curNode.right--;
            }
            if(curNode.left<=curNode.right){
                res.add(strb1.toString()+ch+strb2.toString());
            }
            if(curNode.left<curNode.right){
                    strb1.append(ch);
                    strb2.insert(0,ch);
                int left_temp = curNode.left;
                int right_temp = curNode.right;
                curNode.left++;
                curNode.right--;
                res.add(strb1.toString()+strb2.toString());
                DFS(list.get(left_temp)+1,list.get(right_temp)-1,strb1,strb2,keySet,map,locations,res);
                strb1.deleteCharAt(strb1.length()-1);
                strb2.deleteCharAt(0);                    
            }
            curNode.left = left_Copy;
            curNode.right = right_Copy;
        }
   
    }
   
        public static void main(String[] args) {
                List <String> results = findAllPalindromicSubsequences("abcbabvewreberbervwevwvcba");
                for(String str: results){
                    System.out.println(str);
                }
        }

亲测在大数据下，目前此解法效率最高。如果有更好解法欢迎分享。

膜拜大神。
map是不是使用TreeSet会更简洁一点。