public String preProcess(String s){
        int n =  s.length();
        if(n == 0)
            return "";
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append('#');
            sb.append(s.charAt(i));
        }
        sb.append('#');
        return sb.toString();
    }