4
$\begingroup$

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)$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

With a little care your own suggestion can be implemented to $O(kn)$, if my idea is correct.

Keep $k$ pointers, one for each colour, and a general pointer, the possible start of the segment. At each moment each of these colour pointers keeps the next position of its colour, that follows the segment pointer. One colour pointer points to the segment pointer. That colour pointer is updated when the segment pointer moves to the next position. Each colour pointer in total moves only $n$ positions. For each position the segment pointer computes the maximal distance to the colour pounters, and one takes the overal minimum of that.

Or, intuitively perhaps simpler, let the pointers look into the past, not the future. Let the colour pointers denote the distance to the respective colours last seen. In each step add the distance to the last bead to each pointer, except the one of the current colour, which is set to zero.

(edit: answer to question) If $k$ is large, in the order of $n$ as suggested, then one may keep the $k$ pointers in a max heap. An update of a pointer costs $\log k$ each of $n$ steps. We may find max (the farthest colour, hence the interval length) in constant time, each of $n$ steps. So $n \log k$ total plus initialization.

Now we also have to find the element/colour in the heap that we have to update. This is done by keeping an index of elements. Each time we swap to elements in the heap (a usual heap operation) we also swap the positions stored in the index. This is usually doen when computing Dijkstra's algorithm with a heap: when a new edge is found some distances to vertices have to be decreased, and one needs to find them.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nice! Thank you! However, since $k$ can be $O(n)$, this will also be $O(n)$. But I'm sure it will be faster than the brute force algorithm that I suggested. Can we go faster than quadratic, even when $k$ is $O(n)$? $\endgroup$
    – mayank
    Commented Dec 10, 2012 at 9:41
  • $\begingroup$ Great idea! I'm hitting a roadblock though. If I have understood your algorithm (the first one in your answer), then we will need to update some internal value of the heap. When we want to move to the next starting position, the colour pointer at the current starting position will need to be updated to the next position of that colour. This will require modifying an internal value of the max-heap. How can this be done, when the array index (position in the heap's implementation) for this colour pointer is unknown? $\endgroup$
    – mayank
    Commented Dec 10, 2012 at 12:30
  • $\begingroup$ Perhaps a (balanced) binary search tree would be better - min and update would both be $O(\log{k})$? $\endgroup$
    – mayank
    Commented Dec 10, 2012 at 14:47
  • $\begingroup$ Added heap details into answer. Balanced tree will not find max in log k time. It can be used as index though, see my answer, but if the colours are consecutive numbers one uses a table for storing positions. $\endgroup$
    – Hendrik Jan
    Commented Dec 10, 2012 at 15:21
  • $\begingroup$ Yep, I did think of storing and updating indices, it just seemed like too much book-keeping. As for using a balanced BST, for each position of bead, we can find max in $O(log{k})$ (right-most node) and then find and update in $O(\log{k})$. I did not understand why max will not be in log k time? But yes, your solution should work nicely. Thanks! $\endgroup$
    – mayank
    Commented Dec 10, 2012 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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