Editorial for SAC '22 Code Challenge 4 P2 - Obligatory String Problem

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

Define a function int distance(string base, string to_grade) that returns the distance from base to to_grade.

The distance between each character can be determined with $\min(abs(a - b), a -$ ~\min(abs(a - b), a - ~a $+$ ~ + ~z $- b + 1)$ ~ - b + 1)~, where $abs(C)$ ~abs(C)~ denotes the absolute value of $C$ ~C~, $a$ ~a~ is the character from base, and $b$ ~b~ is the character from to_grade.

Loop through all possibilities for the first character from a to z.

In that loop, loop through all possibilities for the second character from a to z.

In that loop, loop through all possibilities for the third character from a to z.

In that loop, loop through all possibilities for the fourth character from a to z.

Construct the string from these characters.

If the distance from this string to the base string is less than or equal to $K$ ~K~, output it.

Time Complexity: $\mathcal{O}(4 \times 26^4)$ ~\mathcal{O}(4 \times 26^4)~

Comments

There are no comments at the moment.