@iaming The time complexity O(mn) is implemented by greedy choice, which is "The optimal answer can always be achieved by rotating clockwise or anti-clockwise to the next identical character". If there is an optimal solution by rotating clockwise to the kth identical character, we can get equally optimal solution by rotating clockwise to the first identical one, pressing it, and continuing rotating to the kth one.

For example,

key = "abc", ring = "ddaddabcdddda";

The optimal solution is to rotate anti-clockwise by 5 steps. But you can also rotate anti-clockwise by 2 step, press it, and rotate another 3 steps.

Subcategories

LeetCode Weekly Contest 22