Shortest Non-Subsequence String With Constant-Size Alphabet
For each $i$, let $s(i)$ be a string of length $f(i)+1$ that is not a subsequence of $S[1\ldots i]$, then what you seek for is exactly $s(n)$. Also denote $g(i) = \min\left(\ell\left(i,\sigma_1\right),\ldots,\ell\left(i,\sigma_{|\Sigma|}\right)\right)$. $g(i)$'s can be computed in $O(n)$ time in advance.

We have
$$
s(i)=s(g(i)-1)S[g(i)].
$$
Firstly $s(g(i)-1)S[g(i)]$ is of length $f(i)+1$. Suppose by contradiction $s(g(i)-1)S[g(i)]$ is a subsequence of $S[1\ldots i]$, then the index that the last character $S[g(i)]$ matches must be less than or equal to $g(i)$, which means $s(g(i)-1)$ is a subsequence of $S[1\ldots (g(i)-1)]$, a contradiction. So the recurrence is correct.

Now you can use this recurrence to compute $s(n)$:


Let $i \leftarrow n$, and let $s$ be an empty string.
If $g(i)$ does not exist, which means there is at least one character not appearing in $S[1\ldots i]$, insert this character to the beginning of $s$ and return $s$.
Insert $S[g(i)]$ to the beginning of $s$.
Let $i\leftarrow g(i)-1$.
Go back to step 2.