Editorial for Appleby Contest '20 P3 - Ridiculous String

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

The answer is always |T|.

Time Complexity: \mathcal{O}(1)

Subtask 2

If an answer exists, the prefix of the subsequence of S equal to T must contain at least one character from each copy of s. Thus, we can just copy s |T| times and check that instead.

Time Complexity: \mathcal{O}(|s||T|)

Memory Complexity: \mathcal{O}(|s||T|)

Subtask 3

The solution is the same as the previous subtask except you don't explicitly copy s.

Time Complexity: \mathcal{O}(|s||T|)

Memory Complexity: \mathcal{O}(|s|+|T|)

Subtask 4

Construct an array nxt where nxt[i][j] contains the first index of the letter j in s with an index >i. This array can be used to find the smallest prefix in \mathcal{O}(|T|) time.

Time Complexity: \mathcal{O}(|s|+|T|)


There are no comments at the moment.