PermutationsOfString

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class PermutationsNoDuplicates {

    public static void main(String[] args) {
        printStrings(getAllPermutations("abdc"));

    }

    public static void printStrings(List<String> abc) {
        System.out.println(abc.size());
        for (String s : abc) {
            System.out.println(s);
        }
    }

    public static List<String> getAllPermutations(String s) {
        if (s.length() == 1) {
            return Collections.singletonList(s);
        } else {
            char c = s.charAt(0);
            List<String> permutationsInner = getAllPermutations(s.substring(1,
                    s.length()));
            return insertCharAtAllLocationsInStrings(c, permutationsInner);
        }
    }

    public static List<String> insertCharAtAllLocationsInStrings(char c,
            List<String> strings) {
        List<String> permutations = new ArrayList<>();
        for (String s : strings) {
            List<String> permutationsForS = insertCharAtAllLoc(c, s);
            permutations.addAll(permutationsForS);
        }
        return permutations;
    }

    public static List<String> insertCharAtAllLoc(char c, String s) {
        List<String> strings = new ArrayList<>();
        int locationToInsert = 0;

        // Now iterate through the string
        for (locationToInsert = 0; locationToInsert < s.length() + 1; locationToInsert += 1) {
            char[] array = new char[s.length() + 1];
            for (int j = 0, i = 0; j < s.length() + 1; j++) {
                if (j == locationToInsert) {
                    array[j] = c;
                } else {
                    array[j] = s.charAt(i);
                    i += 1;
                }

            }
            strings.add(String.valueOf(array));
        }
        return strings;
    }
}