# Shortest sequence over alphabet $\{1, 2, …, k\}$ which is not a subsequence of $A$ and $B$

I have two sequences - $A$ (of length $n$) and $B$ (of length $m$). They consist of numbers from the alphabet $\{1, 2, ..., k\}$. How want to find the shortest sequence $C$ such that $C$ is not a subsequence of $A$ and $C$ is not a subsequence of $B$? It should be made from numbers from $\{1, 2, ..., k\}$. For example if $k = 2$, $A = 1,1,1,2,2,2$ and $B = 2,2,2,1,1,1$ then the shortest sequence $C$ has length $3$ and an example would be $C = 2,1,2$

• I guess that, in your example, the alphabet is $\{1,2\}$; otherwise, a shorter solution would be $C = 3$. – Mario Cervera Jan 17 '17 at 10:32
• Yes, $k = 2$ in my example – user128409235 Jan 17 '17 at 10:35
• Have you looked at this question and the answers? cs.stackexchange.com/questions/39687/… – Peter Leupold Jan 17 '17 at 15:05