## 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:

#### Subtask 1

The answer is always .

**Time Complexity:**

#### Subtask 2

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

**Time Complexity:**

**Memory Complexity:**

#### Subtask 3

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

**Time Complexity:**

**Memory Complexity:**

#### Subtask 4

Construct an array where contains the first index of the letter in with an index . This array can be used to find the smallest prefix in time.

**Time Complexity:**

## Comments

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

Fixed, thanks!