Chaîne de non-subséquence la plus courte avec alphabet de taille constante

Question

Soit $ s [1..n] in Sigma ^ * $ une chaîne de symboles $ n $ sur l'alphabet $ Sigma $ où $ | Sigma | in mathcal {o} (1) $. Déterminez une chaîne la plus courte qui ne peut pas être obtenue à partir de $ s $ en supprimant certains (peut-être pas) symboles.

Par exemple, on nous donne $ sigma = {a, c, g, t } $ et $ s = acgtacgt $. Dans ce cas, une réponse valide est $ CCA $, car elle ne se produit pas comme une sous-séquence dans $ s $ (c'est-à-dire ne peut pas être obtenue en supprimant certains des symboles de $ s $) et il n'y a pas une telle chaîne de longueur 2 $ .

Je recherche un algorithme qui prend $ mathcal {o} (n) $ ou $ mathcal {o} (n log n) $ time. Il n'est pas suffisant pour calculer la longueur de la réponse, un exemple doit également être construit.

Observations et approches. La longueur de la réponse ne dépasse pas $ displaystyle frac {n} {| Sigma |} + 1 $ par Pigeonhole Principle. Cette limite supérieure est atteinte pour $ s = acgtacgt ... acgt $ dans l'exemple ci-dessus. Si nous ne sommes intéressés que par la durée de la réponse, l'approche suivante devrait fonctionner. Soit $ f (i) $ le plus gros $ k in mathbb {n} $ tel que chaque chaîne de longueur $ k $ est une sous-séquence du préfixe $ s [1..i] $. Notre réponse finale est $ f (n) + 1 $ et $ f $ peuvent être calculées par programmation dynamique dans $ mathcal {o} (n) $ time pour 1 le i le n $ simplement par récidive

$ displayStyle f (i) = 1 + f Left ( min {( ell (i, Sigma_1), ell (i, Sigma_2), Dots, ell (i, Sigma_ {| Sigma |})) - 1} droite) $

où $ ell (i, sigma) $ désigne la dernière occurrence de $ sigma in sigma $ dans le préfixe $ s [1..i] $. De toute évidence, la fonction $ f $ augmente, c'est-à-dire $ f (i + 1) ge f (i) $ pour 1 le i le n - 1 $. Il semble plus difficile de construire un exemple à partir de ces informations, c'est là que je suis coincé.

Enfin, notez que le problème est beaucoup plus facile, si nous avons besoin que la sous-séquence soit continu. Puisqu'il n'y a que $ mathcal {o} (n ^ 2) $ substrations, mais $ mathcal {o} (| Sigma | ^ k) $ cordes de longueur $ k $ sur $ Sigma $, $ k $ tourne être très petit et même une force brute réussira.

Tout type d'aide est apprécié, merci d'avance.

Source d'origine: ensemble de problèmes CSES (https://cses.fi/problemset/task/1087/).