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!