Print all possible strings of length k formed from set of n characters without repetitive structure

Question

Print all possible strings of length k formed from set of n characters is a common question and already have solution.

However, I hope to know

Question: Is there any way to Print all possible strings without repetitive structure ?

Repetitive Structure Examples [k = 3, n = {a, b, c}]:

1. AAA = BBB = CCC
2. ABB = ACC = BAA = BCC = CAA = CBB
3. ABC = ACB = BAC = BCA = CAB = CBA
4. ABA = ACA = BAB = BCB = CAC = CBC
5. AAB = AAC = BBA = BBC = CCA = CCB

For Example:

Input: k=3, n={a,b,c}

Output:

aaa
aab
aba
abb
abc

For the complexity requirement: It should not greater than O(n^k).

Answer 1

You can adapt the existing solution. The restriction you need to add is that a character can only appear in the string after all the other characters before it in the list have appeared at least once. This works because for each set of strings with the same repetitive structure, there is only one where the first appearance of each character is in the order they appear in the list, so this is the one you output. You can enforce this restriction with an extra parameter:

static void printAllKLengthRec(char[] set, 
                            String prefix, 
                            int n, int k, int validCount)
{

    // Base case: k is 0, print prefix
    if (k == 0) 
    {
        System.out.println(prefix);
        return;
    }

    // One by one add all valid characters and recursively call for k equals to k-1
    for (int i = 0; i < validCount; ++i)
    {

        // Next character of input added
        String newPrefix = prefix + set[i]; 

        // increment the valid count if all characters up till then have already
        // appeared and there are characters that have not yet appeared
        // (i.e. validCount < n)
        int newValidCount = (i == (validCount - 1)) && (validCount < n) ?
            validCount + 1 :
            validCount;

        // k is decreased, because we have added a new character
        printAllKLengthRec(set, newPrefix, 
                                n, k - 1, newValidCount); 
    }
}

So for example if your set is {'a', 'b', 'c', 'd'} and validCount is 3 then it means a and b have already appeared and so a or b or c can be appended to the string. If you append c then increment the value before calling the function recursively, because now a and b and c have appeared at least once and so d can now be appended. If you append a or b then the value will remain the same.

For the first character in the permutation, only the first character in list can appear:

static void printAllKLength(char[] set, int k)
{
    int n = set.length; 
    printAllKLengthRec(set, "", n, k, 1);
}