import java.util.Arrays;

public class Anagram {
	public static void main(String[] args) {
		System.out.println(Arrays.toString(subAnagram("dirty", 1)));
	}

	public static String[] subAnagram(String input, int n) {
		int inputLength = input.length();
	        String[][] result = new String[inputLength][];

        	// recursive
		if(inputLength <= n) {
			// special case
			if(inputLength == 2) {
				String[] returnValue = new String[2];
				returnValue[0] = input.substring(1, 2) + input.substring(0, 1);
				returnValue[1] = input;
				return returnValue;
			} else if(n == 1 && inputLength == 1) {
				return new String[]{input};
			}
			//default case
			for(int i = 0; i < inputLength; i++) {
				String[] resultFromAnagram = subAnagram(input.substring(0, i) + input.substring(i+1), n);
				for(int j = 0; j < resultFromAnagram.length; j++) {
					resultFromAnagram[j] = input.substring(i, i+1) + resultFromAnagram[j];
				}
				result[i] = resultFromAnagram;
			}
		} else {
			for(int i = 0; i < inputLength; i++) {
				result[i] = subAnagram(input.substring(0, i) + input.substring(i+1), n);
			}
        	}

        	// convert 2D array to 1D Array
		String[] processedResult = new String[result.length * result[0].length];
		for(int i = 0; i < result.length; i++) {
			for(int j = 0; j < result[0].length; j++) {
				processedResult[j + (i*result[0].length)] = result[i][j];
			}
		}

        	// find number of Original value in array
		int lengthOfnewArray = 0;
		for(int i = 0; i < processedResult.length; i++) {
			for(int j = i-1; j >= 0; j--) {
				if(processedResult[i].equals(processedResult[j])) {
					lengthOfnewArray--;
					break;
				}
			}
			lengthOfnewArray++;
		}

        	// Create new Array without dulicated value
		if(processedResult.length == lengthOfnewArray) {
			return processedResult;
		} else {
			String[] finalResult = new String[lengthOfnewArray];
			int count = 0;
			for(int i = 0; i < processedResult.length; i++) {
				if(!Arrays.asList(finalResult).contains(processedResult[i])) {
					finalResult[count] = processedResult[i];
					count++;
				}
				if(count >= lengthOfnewArray) {
					break;
				}
			}
			return finalResult;
		}
	}
}