### jonathanesmuyguapo's blog

By jonathanesmuyguapo, history, 6 weeks ago,

A few days ago I found a problem called Weird Keyboard in the Progvar problemsets under the category of DP classics with twists (Progvar is now down sadly, but the problem is still accessible).

I couldn't manage to solve it on my own, and I didn't find any solutions online either, but a friend of mine provided a solution using DP with Trie, which he got AC with. I cannot explain his solution too well, since I haven't learnt any string algorithms/structures yet, but in case anyone is interested, you can see his code here (excuse the long template).

Can anyone think of a solution to this problem that doesn't make use of any string algorithms/structures? Or any alternative solution at all?

Thanks!

TLDR version of the problem statement: Given a string $T$, and $k$ strings $S_1 .. S_k$, find a way to concatenate strings $s_i$ in any order (repetitions are allowed, you may also not use some strings) such that it minimizes the edit distance with string $t$. You only need to output the minimum edit distance. It's not necessary to construct the actual string. $|T| <= 4000$ , $k <= 4000$ and $|S_1| + ... + |S_k| <= 4000$

• +17