Editorial for RGPC '17 P5 - Scrabble Nuts
Submitting an official solution before solving the problem yourself is a bannable offence.
This problem is simply minimum edit distance, but requires you to calculate the edit distance to all of the prefixes of a word. Given two strings and , the edit distance between them is the minimum number of operations (insertions/deletions/swaps) required to transform into .
Using dynamic programming, the time complexity of minimum edit distance is , which will pass, but since you require an array of size , you will run out of memory. To save memory, only store the previous row of states, because anything more is unnecessary. To calculate the final answer, loop through each state and add its value to your result.