# Permuting letters within three-letter substrings of strings over $\{\mathsf{x},\mathsf{y},\mathsf{z}\}$ to yield a target “cyclic string”

Given a string made up of only letters $\mathsf{x}$, $\mathsf{y}$ and $\mathsf{z}$, we need to determine whether it can be changed into a string such that each three-letter substring of the string is either $\mathsf{xyz}$, $\mathsf{yzx}$ or $\mathsf{zxy}$. The only operation permitted is we can select a substring of length three that is not one of these three forms and then rearrange the three letters in any order.

Note that each target string is of the form either $\mathsf{xyzxy\ldots}$ or $\mathsf{yzxyz\ldots}$ or $\mathsf{zxyzx\ldots}$, and is in this sense cyclic.

Now, in the given string the counts of each letter $\mathsf{x}$, $\mathsf{y}$ and $\mathsf{z}$ is such that a cyclic string is possible (e.g., if the string has $8$ characters, then two of the letters must have three occurrences in the string, and the third letter two occurrences). Now, it is necessary to prove that we can rearrange the letters using the permitted operation and create a cycle.

I am confused at this part. How to prove that within a finite number of such operations, we can indeed obtain a cycle?

Example:

• Suppose the given string is $\mathsf{xxyyyzzz}$, so the $\mathsf{x}$-count is $2$, the $\mathsf{y}$-count is $3$, and the $\mathsf{z}$-count is $3$. We can see that the cycle obtainable from the given string is $\mathsf{yzxyzxyz}$ ($\mathsf{x}$-count $2$, $\mathsf{y}$-count $3$, $\mathsf{z}$-count $3$).

Now we need to apply the operation of selecting a three-letter substring not equal to either $\mathsf{xyz}$, $\mathsf{yzx}$ or $\mathsf{zxy}$. We can try rearranging using the allowed operation and we can see that we can finally obtain the string $\mathsf{yzxyzxyz}$ from $\mathsf{xxyyyzzz}$.

And guys, when solving such problems, I sometimes get solution intuitively but can't find a proof. And this tenses me much because I can't prove why its correct. So any tips about it would be helpful (how to attack and get a proof).

You always can move a badly placed letter to the first place where it's well placed, isn't it enough ?

As an example if you have :

$_x$xyzxyzxyz

xy$_x$zxyzxyz

xyzx$_x$yzxyz

xyzxy$_x$zxyz

xyzxyzx$_x$yz

xyzxyzxyz$_x$

It's equivalent to say that you always can "move" a well formed subpart of the string to form a biger one (if the number of each letter allows a solution)

as an exemple :

...xxxx$_{xyz}$yyyx...

...xxxx$_{yxyz}$yyx...

...xxxxy$_{yxyz}$yx...

...xxxxyy$_{yxyzx}$...