'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List


class Solution:
    # S: O(n^2)
    # T: O(n^4)
    def encode(self, s: str) -> str:
        n = len(s)
        
        # dp[i][j] = s[i : j+1], so i and j are inclusive
        dp = [[""] * n for _ in range(n)]
        
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                cur_s = s[i: j+1]
                
                dp[i][j] = cur_s
                
                if len(cur_s) > 4: # if == 4 or < 4, compressing doesn't make is shorter
                    # try all possible splits
                    for k in range(i, j):
                        if len(dp[i][k] + dp[k+1][j]) < len(dp[i][j]):
                            dp[i][j] = dp[i][k] + dp[k+1][j]
                    # try to compress the string
                    # use prefix of cur_s as potential patterns
                    for k in range(i, j+1): # cur_s = s[i:j+1]
                        pattern = s[i: k+1] # -> dp[i][k]
                        
                        if pattern and len(cur_s) % len(pattern) == 0 and \
                            cur_s.replace(pattern, "") == "":
                                candidate = str(len(cur_s)//len(pattern)) + \
                                    "[" + dp[i][k] + "]"
                                
                                if len(candidate) < len(dp[i][j]):
                                    dp[i][j] = candidate
                                    
        return dp[0][n-1]
                        
        