public static ArrayList<String> getPermutations(String s) {
        if (s == null) return null;
        ArrayList<String> result = new  ArrayList<String>();
        // Even no need to have s.length()==1 base case
        if (s.isEmpty()) {
            result.add(s);
            return result;
        }
        ArrayList<String> lastStrings = getPermutations(s.substring(1));
        for (String lastString : lastStrings) {
            for (int i = 0; i <= lastString.length(); ++i) {
                result.add(lastString.substring(0, i) +
                           s.charAt(0) +
                           lastString.substring(i));
            }
        }
        return result;
    }