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

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 210 |

2 | awoo | 188 |

3 | Errichto | 186 |

4 | rng_58 | 185 |

5 | SecondThread | 182 |

6 | Ashishgup | 176 |

6 | Um_nik | 176 |

8 | maroonrk | 174 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2021 06:27:47 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

nota subsequence. How? We can explicitly construct it as the last character in each of the partitions, plus some characternotin the incomplete subsegment (or any character, if there is no incomplete subsegment).Thanks a lot.

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?

Very nice explanation dude

Can you explain why this is the optimal way?

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

Ohh!! We have greedily selected the minimum possible. thanks :)

How do we construct lexicographically smallest non-subsequence(of length k+1 ) after finding maximal k?