Find longest subsequence that contains letters with the same frequency in order

user_11872065 0
Viewed 201

This is a question from the 2019 Australian Informatics Olympiad Competition:

After the success of your latest research project in mythical DNA, you have gained the attention of a most diabolical creature: Medusa. Medusa has snakes instead of hair. Each of her snakes’ DNA is represented by an uppercase string of letters. Each letter is one of S, N, A, K or E. Your extensive research shows that a snake’s venom level depends on its DNA. A snake has venom level x if its DNA:

• has exactly 5x letters • begins with x copies of the letter S

• then has x copies of the letter N

• then has x copies of the letter A

• then has x copies of the letter K

• ends with x copies of the letter E.

For example, a snake with venom level 1 has DNA SNAKE, while a snake that has venom level 3 has DNA SSSNNNAAAKKKEEE. If a snake’s DNA does not fit the format described above, it has a venom level of 0. Medusa would like your help making her snakes venomous, by deleting zero or more letters from their DNA. Given a snake’s DNA, can you work out the maximum venom level this snake could have?

Is it possible using binary search to obtain an algorithm with complexity O(nlogn)?

algorithm
2 Answers

Yes you can use binary search to search for maximum venom level.

initially: l=0 r=n

when for some m=(l+r+1)/2 we can check in O(n) time if we can obtain such venom level m, just by taking first m letters S then next m letters N and so on. If there's not enough letters we update our search interval to r=m-1 otherwise l=m

Example: suppose input is SNAKESSSNNAAKKE

  1. Binary search initial values: l=0 r=15
  2. l=0 r=15 m = (l+r+1)/2 = 8
  3. we cant get venom value of 8 so r=m-1 = 7
  4. l=0 r=7 m = (l+r+1)/2 = 4
  5. we cant get venom value of 4 so r=m-1 = 3
  6. l=0 r=3 m = (l+r+1)/2 = 2
  7. we can get venom value of 2 so l=m = 2
  8. l=2 r=3 m = (l+r+1)/2 = 3
  9. we cant get venom value of 3 so r=m-1 = 2
  10. now since l==r we terminate binary search and conclude that answer is 2
user_40591450

Linear time, linear space:

Say the input string has length n. Make a 5xn array, where the 5 rows represent the cumulative count of S, N, A, K, E for each index in the input array. Let's call these rows S, N, A, K, and E.

Keep track of 5 indices, let's call them s, n, a, k, and e.

Increment `s` until `S[s]` increases by 1 (possibly at s=0). 
Increment `n` until `N[n]-N[s]=S[s]`.
Increment `a` until `A[a]-A[n]=S[s]`.
Increment `k` until `K[k]-K[a]=S[s]`.
Increment `e` until `E[e]-E[k]=S[s]`.

Repeat as many times as you can. The final number for which we are able to satisfy the increment steps gives us the answer.

There are 5n indices amongs the arrays, and we only ever increment them, so this is linear in n.

There are some obvious optimizations to improve this, but it can't be improved beyond linear.

Linear time, constant space

We'll use the same index names as before, but will let the capital letters represent cumulative occurances of S, N's after the last S, K's after the last N, and so on.

Set `s` to the first index where an S appears.
Set `n` to `s`, and increment until we get an N.
Set `a` to `n`, and increment until we get an A.
Set `k` to `a`, and increment until we get an K.
Set `e` to `k`, and increment until we get an E.

Now, repeatedly do the following:

Increment s until we get another S, decrementing N, A, K, E each time we find the matching letter at an index <= the value of n, a, k, e respectively.

Set n=s and increment n, adding 1 to N for each N we find, until N=S

Do the same for for a, k, e.

As before, the final time we're able to complete this, we've found the DNA of the snake.

user_20410770
Related