I read this question somewhere, and could not come up with an efficient answer.
A string of some length has beads fixed on it at some given arbitrary distances from each other. There are $k$ different types of beads and $n$ beads in total on the string, and each bead is present atleast once. We need to find one consecutive section of the string, such that:
- that section contains all of the $k$ different types of beads atleast once.
- the length of this section is as small as possible, provided the first condition is met.
We are given the positions of each bead on the string, or alternatively, the distances between each pair of consecutive beads.
Of course, a simple brute force method would be to start from every bead (assume that the section starts from this bead), and go on till atleast on instance of all beads are found while keeping track of the length. Repeat for every starting position, and find the minimum among them. This will give a $O(n^2)$ solution, where $n$ is the number of beads on the string. I think a dynamic programming approach would also probably be $O(n^2)$, but I may be wrong. Is there a faster algorithm? Space complexity has to be sub-quadratic. Thanks!
Edit: $k$ can be $O(n)$.