Problem statement

https://leetcode.com/problems/encode-string-with-shortest-length/

Solution

This is difficult dp problem. Let dp[i][j] be a string with minimum length of encoded substring s[i:j+1]. For each of O(n^2) sub-strings, we first check if it is repetition of some other substring, see problem 0459 Repeated Substring Pattern. We can do it in O(n) time. Next step is to try to split string to two parts in O(n) ways and evaluate sums for each split.

Complexity

Overall time complexity is O(n^4), because we have O(n^2) different states and for each state we need to work with O(n) pairs of strings with length O(n). Space complexity potentially also O(n^3), because we can keep a lot of encoded strings.

Code

class Solution:
    def encode(self, s):
        n = len(s)
        dp = [[""] * n for _ in range(n)]
        for l in range(n):   #length
            for beg in range(n-l):
                end = beg + l

                dp[beg][end] = s[beg: end + 1]
                if l < 4: continue

                q = dp[beg][end]
                ind = (q + q)[1:-1].find(q) + 1
                if ind != 0:
                    ss = str((l+1) // ind) + "[" + dp[beg][beg+ind-1] + "]"
                    dp[beg][end] = min(dp[beg][end], ss, key = len)
                
                for k in range(beg, end):
                    dp[beg][end] = min(dp[beg][end], dp[beg][k] + dp[k+1][end], key = len)

        return dp[0][-1]