Suppose you are given a fixed size alphabet $\Sigma$ and a string $S$ of length $n$ over it.
The task is to find a shortest length string (formed using letters in $\Sigma$) which is *not* a substring of $S$.
Any shorter string will be a substring of $S$.
For example, if $\Sigma = \{0, 1\}$ and $S = 01100$, then a shortest length string will be of length $3$ (for e.g: $000$ will do).
Can you do it in $O(n)$ time?
[Solution]
The task is to find a shortest length string (formed using letters in $\Sigma$) which is *not* a substring of $S$.
Any shorter string will be a substring of $S$.
For example, if $\Sigma = \{0, 1\}$ and $S = 01100$, then a shortest length string will be of length $3$ (for e.g: $000$ will do).
Can you do it in $O(n)$ time?
[Solution]
No comments:
Post a Comment