Shortest subsequence containing all elements
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] &gt; 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] &gt; 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 &lt; 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