Given strings $x$ and $y$, a template length $l$, and a maximum number of different templates $k$, the task is to determine if it's possible to convert $x$ into $y$ using no more than $k$ different templates, each of exactly length $l$. For example, if $x = AAA$, $y = ABC$, $l = 2$, and $k = 2$, the answer would be YES because it's feasible to achieve the transformation with just two different templates of length 2. For example $AB$ to get $ABA$ and then $BC$ to get the desired $ABC$.
The goal would be to prove that this problem is NP-hard by reducing a known problem to this problem. I've tried many problems but never successfully. Thanks for your help!
EDIT:
A template is a string of length $l$ (fixed for all templates and given as a parameter of the problem) that is composed of the letter of the alphabet ($A$ to $Z$). It can be 'printed' onto the original string. It will replace all the characters that were present in the section of the string where the template is applied.
To clarify the use of templates, here is a more detailed example:
Let’s take $x = AAAAAA$. If the first template is set to be $t_1 = ADF$, we could choose to ‘print’ $t_1$ at position 1 of $x$, resulting in $ADFAAA$. If we decide to use another template $t_2 = XYZ$, we could then ‘print’ that at position 4 of the string to get $ADFXYZ$. We could then choose to use the first template $t_1 = ADF$ again at position 2 to obtain $AADFYZ$. We cannot 'print' these templates at positions 5 or 6, as that would cause an attempt to write $t$ out of bounds (every character of $t$ needs to align with an existing character of $x$).
