LC: 471. Encode String with Shortest Length - spiralgo/algorithms GitHub Wiki

471. Encode String with Shortest Length:

The Essence:

Let's say that there is a string S that can be encoded with two strings a and b. ( encode(S) = a+b ) It can be assumed that the string a encodes the substring in range [0:e]. Then, b encodes [e+1:len].

For each substring in the range [a:b], we can denote its best encoding with best[a][b].

Then, the best encoding of the entire string is basically the concatenation of two best values for each index i. The minimum can be found by checking all these with searching the minimum: best[0][len] = min{ best[0][i] + best[i+1][len] }

Since the optimal solutions to previous problems can be used to solve further problems, this satisfies the properties of dynamic programming. For each index i, the substring [0:i] also needs to be encoded. In addition to this, [j:i], j≤i will also need to be encoded to find through the formula: best[0][i] = min{ best[0][j-1] + best[j][i] }

Therefore, step by step, the program should calculate the most optimal encodings for each substring and combine them at the end to create the solution for the entire string.

Details:

As different ranges can contain substrings with the same string value, caching the encodings for the substring can also be useful. For checking if a substring has patterns, many techniques can be used, e.g. methods from KMP-matching, matching with modulo etc. The implementation of such approaches and their detailed explanation can be found here: https://github.com/spiralgo/algorithms/pull/386