2
$\begingroup$

Given a sequence $a_1,\ldots,a_n$, find the shortest subsequence $a_i,\ldots,a_j$ such that $\{a_1,\ldots,a_n\} = \{a_i,\ldots,a_j\}$.

I came up with three solutions:

The most straightforward brute-force solution is $O(n^3)$.

We can optimizing brute-force solution, performing a binary search on subsequence length in the outermost loop in $O(n^2 \log n)$.

We can re-use idea from longest common subsequence problem by putting tree-based sets in the table (let's say, elements are comparable with $<$) with copy-on-write implementation. This would be $O(n^2 \log m)$, where $m$ is the number of different elements.

Could it be done better? Maybe, something like Z-functions for all different values in $O(nm)$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Usually, the length of a subsequence means the number of terms in that subsequence. For example, in the problem of longest common subsequence. However, in this question and the answer by Yuval below, the length of a subsequence $a_i,\ldots,a_j$ is defined as $j - i$. $\endgroup$
    – John L.
    Dec 7, 2020 at 21:52
  • 1
    $\begingroup$ Here is an equivalent question that is clearer. Given an array $a_1,\ldots,a_n$, find the shortest subarray $a_i,a_{i+1},\ldots,a_j$ such that $\{a_1,a_2, \ldots,a_n\} = \{a_i, a_{i+1},\ldots,a_j\}$. $\endgroup$
    – John L.
    Dec 7, 2020 at 21:55
  • $\begingroup$ This problem would be very easy if you need to find a subsequence. Do you mean substring, which is a harder problem? $\endgroup$
    – Nayuki
    Dec 8, 2020 at 1:43
  • $\begingroup$ Better stated: given a string that contains every letter of some alphabet, find the shortest substring that also contains every letter of the alphabet. $\endgroup$
    – Mike Spivey
    Dec 8, 2020 at 9:56

1 Answer 1

Reset to default
6
$\begingroup$

Start by computing the set of all elements in the input sequence. This takes time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ using a hash table.

Suppose there are $m$ such elements $x_1,\ldots,x_m$. Initialize a histogram $H$ of length $m$ with zeroes, and a counter $C$ to $m$. Go over the elements in the sequence from left to right. When processing $a_i$, update $H[a_i] \gets H[a_i] + 1$ (the indexing operation takes time $O(\log n)$ if we are only allowed comparisons, and $O(1)$ using a hash table), decreasing $C$ if $H[a_i]$ were zero. Stop once $C = 0$. If we stopped at $a_j$, then this means that $a_1,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_1$.

Now update $H[a_1] \gets H[a_1] - 1$. If after the update $H[a_i] > 0$, then $a_2,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_2$. Otherwise, continue scanning the sequence, updating $H$ as before, until $H[a_1] > 0$. If we stopped at $a_j$, that $a_2,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_2$.

In this way we can find the lengths of all shortest subsequences containing all elements and starting at $a_i$, for each $i$. We output the length of the shortest one. The entire algorithm runs in time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ otherwise.

In the latter case, $O(n)$ is optimal, as a simple adversary argument shows (whenever the algorithm accesses an element, answer $1$; even after accessing all but one element, the algorithm cannot tell whether the correct answer is $1$ or $2$).

If we are only allowed comparisons, then we can get an $\Omega(n\log n)$ lower bound from Element Distinctness. Suppose that we could solve our problem using $T(n)$ comparisons. Given a sequence $a_1,\ldots,a_n$, consider the sequence $a_1,\ldots,a_n,a_1,\ldots,a_n$. If all elements are distinct, the shortest subsequence containing all elements has length $n$. Otherwise, if $a_i = a_j$ for $i < j$ then the subsequence $a_{i+1},\ldots,a_n,a_1,\ldots,a_{i-1}$ contains all elements and has length $n-1$. This shows that we can solve Element Distinctness in time $T(2n)$. The well-known lower bound $\Omega(n\log n)$ on Element Distinctness implies that $T(2n) = \Omega(n\log n)$, and so our algorithm is optimal. (Formally speaking, we also need to handle odd input lengths. We can do this by adding a fresh element between the two copies of the original sequence.)

Credit for the algorithm: https://www.glassdoor.com/Interview/Find-shortest-substring-in-a-string-that-contains-all-of-a-set-of-characters-QTN_66124.htm

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ At each stage, we have hold of a segment a[lo..hi) and keep track of the number of times H[x] each element x appears in the segment, and also the number of elements C that do not appear; it is easy to update H and C when lo or hi is incremented. At each stage, if C = 0 we note a solution and increment lo, and if C > 0, we increment hi. We can stop when both hi = n and C > 0. $\endgroup$
    – Mike Spivey
    Dec 8, 2020 at 10:01
  • $\begingroup$ So do I understand correctly that the interval crawls like a caterpillar or worm? Expanding until all different items are covered and contracting while all items are covered? $\endgroup$
    – kirilloid
    Dec 8, 2020 at 10:55
  • 1
    $\begingroup$ Yes, that’s the idea. $\endgroup$
    – Yuval Filmus
    Dec 8, 2020 at 12:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.