A valid encoding of an array of strings words consists of a reference string s and an array of indices indices satisfying the following conditions:

• words.length is equal to indices.length.

• For each index i, the substring of s starting at indices[i] and extending up to the next '#' character is equal to words[i].

Given an array of strings words, return the minimum possible length of any reference string s that validly encodes words.

Constraints:

• $1 \leq$ words.length $\leq 2000$

• $1 \leq$ words[i].length $\leq 7$

• words[i] consists of only lowercase letters.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.