Editorial for DMOPC '20 Contest 5 P1 - Home Row - Olympiads Online Judge

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$ ~S~ and $T$ ~T~. Thus, our answer is simply $|S| + |T| - 2 \times |LCP(S, T)|$ ~|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|))$ ~\mathcal{O}(\min(|S|, |T|))~, and that is sufficient to solve the problem.

Time Complexity: $\mathcal{O}(|S| + |T|)$ ~\mathcal{O}(|S| + |T|)~

Comments

There are no comments at the moment.