package stringpermutations;

import java.util.Map;
import java.util.TreeMap;

class StringPermutation {
	
	private static char[] array;
	private static char[] chars;
	private static int[] count;
	private static char[] result;
	
	private static void printCharArray(char[] array) {
		for(char ch: array) {
			System.out.print(ch);
		}
		System.out.println();
	}
	
	private static void run() {
		Map<Character, Integer> map = new TreeMap<>();
		
		for(char ch: array) {
			map.compute(ch, (key, val) -> {
				if(val == null) {
					return 1;
				} else {
					return val + 1;
				}
			});
		}
		
		int index = 0;
		for(Map.Entry<Character, Integer> entry: map.entrySet()) {
			chars[index] = entry.getKey();
			count[index] = entry.getValue();
			index++;
		}
		
		permute(0);

	}
	
	private static void permute(int level) {
		if(level == chars.length) {
			printCharArray(result);
			return;
		}
		
		for(int i=0; i < chars.length; i++) {
			
			if(count[i] == 0) {
				continue;
			}
			
			result[level] = chars[i];
			count[i]--;
			permute(level + 1);
			count[i]++;
			
		}
	}
	
	public static void main(String args[]) {
		String str = "AABC";
		
		array = str.toCharArray();
		chars = new char[str.length()];
		count = new int[str.length()];
		result = new char[str.length()];
		
		run();
		
	}

}