## Editorial for CCC '24 J4 - Troublesome Keys

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

It can take some time to wrap your head around the behaviour of Alex's strange keyboard. To help us discuss it here, we will refer to the following five values.

`pressed`

– the first line of input representing the keys pressed by Alex

`displayed`

– the second line of input representing the letters displayed on the screen

`silly`

– the letter corresponding to the silly key

`wrong`

– the letter displayed when the silly key is pressed

`quiet`

– the letter corresponding to the quiet key

For the first subtask, the quiet key is not pressed which means that the letter in `pressed`

that is not in `displayed`

must be `silly`

. Also, `wrong`

must be the letter that is in `displayed`

but not in `pressed`

. Finding a character that appears in one string but not the other can be done with a loop and search. The search
can be accomplished with a built-in function or nested second loop. (In general, we can check whether or not the quiet key is pressed by comparing the lengths of `pressed`

and `displayed`

.)

For the other subtasks, we can still begin by determining `wrong`

as above. Similarly, we can determine a pair of letters `x`

and `y`

that correspond to `silly`

and `quiet`

, but we need to work a bit harder to determine whether `x`

corresponds to silly and `y`

corresponds to quiet, or the other way around. For the second subtask, we can use the fact that the first troublesome key pressed is the silly key. Otherwise, one way to do this is to simulate Alex's keyboard by replacing all occurrences of `x`

in `pressed`

with `wrong`

and removing `y`

from `pressed`

. It the result equals `displayed`

then we know that `x`

corresponds to `silly`

and `y`

corresponds to `quiet`

. Otherwise, we know that it is the other way around. To solve the final subtask where a large number of keys are pressed, the number of times we pass over the input strings cannot depend on , the bound on their lengths. This can be achieved by storing the letters in `pressed`

and `displayed`

in a data structure that allows for efficient searches (e.g. a dictionary in Python or `HashMap`

in Java.)

This problem can also be solved without predetermining `wrong`

and candidates for `silly`

and `quiet`

. We can scan `pressed`

and `displayed`

left to right looking for the first place where they differ. For the second subtask, we then immediately know that `silly`

must be the mismatched character in `pressed`

and `wrong`

must be the mismatched character in displayed. To determine `quiet`

(if it was pressed), we can continue scanning until we find a mismatch that does not involve `silly`

. We omit the details here, but for the third and fourth subtasks, we can extend this approach by considering cases and simulating the behaviour of Alex's keyboard once we determine `silly`

or `quiet`

.

## Comments