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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.