4 added 277 characters in body

You could, of course, use brute-force but simplify the search tree by pruning with a backtracking algorithm. However, it intrigues me to think of it in terms of a more elegant approach, like the necklace listed below. Here are some of my working ideas on it thus far...

Start by breaking down the requirements into succint grouping of requisite necessary sequences, and groupings of forbidden sequences.

Since your alphabet has the letters $S_{letters}=${$A,B,...,K,L$} in your specific case of 12 letters, then the string must contain the sets { {$A$}, {$B$}, ..., {$K$}, {$L$} }. Each of the sets must be represented by the string of four repetitions of the letters of the alphabet, therefore your sequence must contain

$e^4$ for $e\in S_{letters}$

Thus the lower bound for the size of the target string is $|S_{letters}|\times4 = 48$.

The sequence $x^4 y^4, x\in S, y\in S$ is forbidden as the substrings of $xxxxyyyy$ will lead to the set {xy} being replicated 3 times:

{x}, {xy}, {xy}, {xy}, {y}.

More strongly, you can also say that sequence $x^3 y^3, x\in S, y\in S$ is forbidden as the substrings of $xxxyyy$ will lead to the set {xy} also being replicated 3 times

{xy}, {xy}, {xy}

Even more strongly, it can be said that $x^3y^2$ is forbidden as is $x^2y^3$ as each leads to a duplicate set sequence {xy},{xy}.

Thus each of the 4-repeats $e_i^4$ must be surrounded by letters which are not duplicated even once, e.g. $e_a e_b e_i^4 e_x e_y$, where $e_i \notin${$e_a, e_b, e_x, e_y$}

In response to a comment below, let me explain that if $e_a=e_i$ or if $e_y=e_i$, then the sequence $e_a e_b e_i^4 e_x e_y$ will contain duplictes:

• If $e_a = e_i$, then $e_i e_b e_i^4 e_x e_y$ leads to $e_i e_b e_i e_i ...$ and $...e_b e_i e_i e_i ...$, both of which belong to the set {$e_b e_i$}

• If $e_y = e_i$, then $e_a e_b e_i^4 e_x e_i$ leads to $...e_i e_i e_i e_x ...$ and $...e_i e_i e_x e_i ...$, both of which belong to the set {$e_i e_x$}

Also in the necessary set are the $\binom{12}{4} = 495$ ways to pick 4 out of the 12 letters of your alphabet. These could be strung together and overlap, but they must be included in the sequence.

3 Added requirement of the 4 non-repeating letters which must be included

Start by breaking down the requirements into succint grouping of requisite necessary sequences, and groupings of forbidden sequences.

Since your alphabet has the letters $S_{letters}=${$A,B,...,K,L$} in your specific case of 12 letters, then the string must contain the sets { {$A$}, {$B$}, ..., {$K$}, {$L$} }. Each of the sets must be represented by the string of four repetitions of the letters of the alphabet, therefore your sequence must contain

$e^4$ for $e\in S_{letters}$

Thus the lower bound for the size of the target string is $|S_{letters}|\times4 = 48$.

The sequence $x^4 y^4, x\in S, y\in S$ is forbidden as the substrings of $xxxxyyyy$ will lead to the set {xy} being replicated 3 times:

{x}, {xy}, {xy}, {xy}, {y}.

More strongly, you can also say that sequence $x^3 y^3, x\in S, y\in S$ is forbidden as the substrings of $xxxyyy$ will lead to the set {xy} also being replicated 3 times

{xy}, {xy}, {xy}

Even more strongly, it can be said that $x^3y^2$ is forbidden as is $x^2y^3$ as each leads to a duplicate set sequence {xy},{xy}.

Thus each of the 4-repeats $e_i^4$ must be surrounded by letters which are not duplicated even once, e.g. $e_a e_b e_i^4 e_x e_y$, where $e_i \notin${$e_a, e_b, e_x, e_y$}

In response to a comment below, let me explain that if $e_a=e_i$ or if $e_y=e_i$, then the sequence $e_a e_b e_i^4 e_x e_y$ will contain duplictes:

• If $e_a = e_i$, then $e_i e_b e_i^4 e_x e_y$ leads to $e_i e_b e_i e_i ...$ and $...e_b e_i e_i e_i ...$, both of which belong to the set {$e_b e_i$}

• If $e_y = e_i$, then $e_a e_b e_i^4 e_x e_i$ leads to $...e_i e_i e_i e_x ...$ and $...e_i e_i e_x e_i ...$, both of which belong to the set {$e_i e_x$}

Also in the necessary set are the $\binom{12}{4} = 495$ ways to pick 4 out of the 12 letters of your alphabet. These could be strung together and overlap, but they must be included in the sequence.

2 added 312 characters in body

Start by breaking down the requirements into succint grouping of requisite necessary sequences, and groupings of forbidden sequences.

Since your alphabet has the letters $S_{letters}=${$A,B,...,K,L$} in your specific case of 12 letters, then the string must contain the sets { {$A$}, {$B$}, ..., {$K$}, {$L$} }. Each of the sets must be represented by the string of four repetitions of the letters of the alphabet, therefore your sequence must contain

$e^4$ for $e\in S_{letters}$

Thus the lower bound for the size of the target string is $|S_{letters}|\times4 = 48$.

The sequence $x^4 y^4, x\in S, y\in S$ is forbidden as the substrings of $xxxxyyyy$ will lead to the set {xy} being replicated 3 times:

{x}, {xy}, {xy}, {xy}, {y}.

More strongly, you can also say that sequence $x^3 y^3, x\in S, y\in S$ is forbidden as the substrings of $xxxyyy$ will lead to the set {xy} also being replicated 3 times

{xy}, {xy}, {xy}

Even more strongly, it can be said that $x^3y^2$ is forbidden as is $x^2y^3$ as each leads to a duplicate set sequence {xy},{xy}.

Thus each of the 4-repeats $e_i^4$ must be surrounded by letters which are not duplicated even once, e.g. $e_a e_b e_i^4 e_x e_y$, where $e_i \notin${$e_a, e_b, e_x, e_y$}

1