Leetcode: 471. Encode String with Shortest Length

Mistake: Misread the problem. The problem doesn't mention that we would have to encode nested strings, but I should have supposed so.
Can we break-down the problem in small and easily to solve parts? Be \(s\) a string. The final solution is either finding a substring of \(s\) that can be repeated enough to reconstruct \(s\) or the concatenation of \(p\) and \(q\) where \(p+q=s\). Time complexity is \(O(n^3)\) and space complexity is \(O(n^2)\).

class Solution:
    def encode(self, s: str) -> str:
        N = len(s)

        @cache
        def dfs(i, j):
            subs = s[i : j + 1]
            best = subs
            for k in range(i, j):
                npart = k - i + 1
                ncopy = len(subs) // npart
                if len(subs) % npart == 0 and s[i : k + 1] * ncopy == subs:
                    cur = f"{ncopy}[{dfs(i, k)}]"
                    if len(cur) < len(best):
                        best = cur
            for k in range(i, j):
                cur = dfs(i, k) + dfs(k + 1, j)
                if len(cur) < len(best):
                    best = cur
            return best

        return dfs(0, N - 1)


assert Solution().encode("aaa") == "aaa"
assert Solution().encode("aaaaa") == "5[a]"
assert Solution().encode("aaaaaaaaaa") == "10[a]"

class Solution:
    def encode(self, s: str) -> str:
        N = len(s)

        @cache
        def dfs(i, j):
            if i == j:
                return s[i]
            if i > j:
                return ""
            ans = s[i : j + 1]
            p = (ans + ans).find(ans, 1)
            k = len(ans) // p
            if k > 1:
                x = f"{k}[{dfs(i, i + p-1)}]"
                if len(x) < len(ans):
                    ans = x
            for k in range(i, j):
                x = dfs(i, k) + dfs(k + 1, j)
                if len(x) < len(ans):
                    ans = x
            return ans

        return dfs(0, N - 1)