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


Comments


  • 3
    JohnstonLiu  commented on Feb. 17, 2021, 1:18 a.m.

    Typo under Subtask 2 explanation: "chracter" should be "character".


    • 3
      Pookmeister  commented on Feb. 17, 2021, 2:13 a.m.

      Fixed, thanks!