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$$$