Had a telephonic interview. I was asked medium to hard questions. It was a string-based question involving dynamic programming. First, the interviewer asked a simple question on strings. Then, they continued with a follow-up and a more complex question. The interviewer was very helpful during the process and pushed me towards the correct approach if I was going in the wrong direction.

Given a dictionary of words, including all their anagrams, find the word with the lowest score. The score is calculated as the distance between adjacent letters in the word. Try to optimize the runtime.