## Editorial for DMOPC '21 Contest 9 P2 - String Puzzle

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

Iterate through both strings simultaneously. Any excess `a`

s in must be merged with another `a`

immediately behind to match the `b`

correctly in . If the character behind is not `a`

or there is an extraneous `b`

in , we can evaluate the case to be impossible.

**Time Complexity:**

#### Subtask 2

Similar to the first subtask, if a character in is less than the target character in , we must repeatedly try to merge it with further characters in until they match. This can be implemented either recursively or iteratively using a stack.

**Time Complexity:**

Alternately, note that if we let be the order of the character in the alphabet, then the quantity remains invariant over all operations. Thus, we can instead imagine repeatedly splitting the characters of back into . For each split, there can be at most one candidate splitting point in , which can be found by binary searching on the prefix sums of .

**Time Complexity:**

## Comments