## Editorial for RGPC '17 P5 - Scrabble Nuts

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

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.

Time complexity:

## Comments