**Solution**

**Encode String with Shortest Length** https://leetcode.com/problems/encode-string-with-shortest-length/

**Memoization: Time: O(N^3)**

- String based problem can be broken down into smaller sized problem involving sub-strings of the larger string.
- For memoization, we generally parameterize a subtring as s(i,j). For DP, we can parameterize it in terms of substrings of length 1, 2, 3, ..., L.
- Given a substring s(i,j), we have three choices for finding minimum encoding:
- X = Do not encode s(i,j)
- Y = Find all repeating patterns and encodings and then choose the minimum length encoding. Length of repeating pattern ranges from N//2 to 1.
- Z = Split s(i,j) into two substrings left and right. s(i,k) and s(k+1,j). If left and right are same, then we have another candidate "2[left]". Now k ranges from i to j-1. Finally choose the minimun length encoding from all these possibilities.
- s(i,j) = min(X, Y, Z, key=len)
- Note: we use min method in Python to find the shortest string based on length.
- Time Complexity: O(N^3) - There are N^2 sub-problems and every sub-problem can be solved in O(N).
- Space Complexity: O(N^2)

```
class Solution(object):
def find_repeating_pattern(self, s):
N = len(s)
min_so_far = s
for i in range(N//2, 0, -1):
if N%i == 0:
if self.test(i, s):
cnt, pattern = N//i, s[0:i]
min_so_far = min("%d[%s]" %(cnt, pattern), min_so_far, key=len) if cnt > 0 else min_so_far
return min_so_far
def test(self, i, s):
pattern = s[0:i]
for j in range(i, len(s)-i + 1,i):
match = s[j:j+i]
if pattern != match:
return False
return True
def helper(self, s, i, j, cache):
if j < i:
return ""
elif i == j:
return s[i]
elif i in cache and j in cache[i]:
return cache[i][j]
else:
cache.setdefault(i, {})[j] = self.find_repeating_pattern(s[i:j+1])
for k in range(i, j):
left, right = self.helper(s, i, k, cache), self.helper(s, k+1, j, cache)
if left == right:
cache[i][j] = min(cache[i][j], left + right, "2[%s]" %(left), key=len)
else:
cache[i][j] = min(cache[i][j], left+right, key=len)
return cache[i][j]
def encode(self, s):
"""
:type s: str
:rtype: str
"""
cache = {}
return self.helper(s, 0, len(s)-1, cache)
```