Editorial for DMOPC '20 Contest 5 P1 - Home Row


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: 4fecta

Note that it is both necessary and sufficient to change all characters that are not part of the longest common prefix of S and T. Thus, our answer is simply |S| + |T| - 2 \times |LCP(S, T)|. A simple loop from the front of both strings is enough to compute the length of the longest common prefix in \mathcal{O}(\min(|S|, |T|)), and that is sufficient to solve the problem.

Time Complexity: \mathcal{O}(|S| + |T| + \min(|S|, |T|))


Comments

There are no comments at the moment.