By padfoot1717, history, 8 months ago,

I am stucked at the problem Shortest subsequence. Can someone kindly explain an optimal algorithm to solve this problem?

• +6

 » 8 months ago, # | ← Rev. 3 →   +20 Suppose we partition the string into $k$ contiguous subsegments such that the letters GCAT all appear at least once each in each partition. Then, it is clear that all $k$-character strings appear as subsequences.We can construct such a partition greedily. Find the shortest prefix of the string that contains all characters GCAT, make that one subsegment, then recurse on the remaining string. Note that this might actually partition it into $k+1$ subsegments, where the last subsegment is incomplete''. The last character in each subsegment (besides the incomplete subsegment) also appears exactly once in that subsegment; greedily, if it appeared earlier in the subsegment, then we could have ended this partition earlier.If $k$ is maximal, then we can show that there exists a $k+1$ length string that is not a subsequence. How? We can explicitly construct it as the last character in each of the partitions, plus some character not in the incomplete subsegment (or any character, if there is no incomplete subsegment).
•  » » 8 months ago, # ^ |   +8 Thanks a lot.
•  » » 8 months ago, # ^ |   +8 Shisuko Great explanation! I have a question. Is it possible to count the number of such subsequences in a reasonable time limit? If possible then what is the approach?
•  » » 6 months ago, # ^ |   +8 Very nice explanation dude
•  » » 5 months ago, # ^ |   0 Can you explain why this is the optimal way?
•  » » » 5 months ago, # ^ |   0 All strings of length at most $k$ appear as a subsequence, so the answer has to be at least $k+1$.But, we can actually do $k+1$. Thus, the minimum is exactly $k+1$.
•  » » » » 5 months ago, # ^ |   +8 Ohh!! We have greedily selected the minimum possible. thanks :)
•  » » 5 weeks ago, # ^ |   0 How do we construct lexicographically smallest non-subsequence(of length k+1 ) after finding maximal k?