Lexicographic ordering with no consecutive repetition

Question

I know algorithm of lexicographic order but in this question we can have repetition of character non-consecutively.And this make me confused.

A good string s is the one which:

1. contains only these letters of the set: [a,b,c]
2. s[i] != s[i+1] string aba, bca,cbc is valid but aaa, abb, aab not valid.

Order of set:[a, b, c]

["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"].

Can you help me out with its algorithm.

Answer 1

You can use a recursive algorithm where you pass the last used letter as a forbidden letter for the next selection. The recursive function gets a size argument so it knows how long the strings should be that it should produce. It then iterates every possible character, but excludes the forbidden one, and calls the function recursively, but with the size reduced. The current character now becomes the forbidden character for the recursive call. When that call comes back with results, it prefixes each of those results with the current character, so that effectively they all increase in size by one character. This is repeated for all other characters that are iterated (except the forbidden one). And all these results are collected into one result set (array), and returned.

I assume the set of characters is provided in lexicographic order (otherwise sort it before using the below algorithm), and that the size of the produced strings is also a parameter given to the algorithm.

Here is a simple JavaScript implementation of that idea:

function combis(chars, size, forbidden="") {
    if (size == 0) { // base case
        return [""];
    }
    let results = [];
    for (let chr of chars) {
        if (chr != forbidden) { // Avoid repetition
            for (let combi of combis(chars, size-1, chr)) {
                results.push(chr + combi); // prefix the returned string
            }
        }
    }
    return results;
}

console.log(combis("abc", 3));