Encode String with Shortest Length

hard dp string

Problem

Encode a string with the smallest length, using k[encoded] for k repetitions.

Inputs = "aaaaaaaaaa"

Output"10[a]"

"aaaaaaaaaa" encodes to "10[a]".

def encode(s):
    n = len(s)
    dp = [["" for _ in range(n)] for _ in range(n)]
    for L in range(1, n + 1):
        for i in range(n - L + 1):
            j = i + L - 1
            sub = s[i:j+1]
            dp[i][j] = sub
            if L > 4:
                for k in range(i, j):
                    if len(dp[i][k]) + len(dp[k+1][j]) < len(dp[i][j]):
                        dp[i][j] = dp[i][k] + dp[k+1][j]
                # repetition test
                idx = (sub + sub).find(sub, 1)
                if idx < L:
                    times = L // idx
                    enc = str(times) + "[" + dp[i][i+idx-1] + "]"
                    if len(enc) < len(dp[i][j]):
                        dp[i][j] = enc
    return dp[0][n-1]

function encode(s) {
  const n = s.length;
  const dp = Array.from({length: n}, () => new Array(n).fill(""));
  for (let L = 1; L <= n; L++) {
    for (let i = 0; i + L - 1 < n; i++) {
      const j = i + L - 1;
      const sub = s.slice(i, j + 1);
      dp[i][j] = sub;
      if (L > 4) {
        for (let k = i; k < j; k++) {
          if (dp[i][k].length + dp[k+1][j].length < dp[i][j].length) {
            dp[i][j] = dp[i][k] + dp[k+1][j];
          }
        }
        const idx = (sub + sub).indexOf(sub, 1);
        if (idx < L) {
          const times = L / idx;
          const enc = times + "[" + dp[i][i+idx-1] + "]";
          if (enc.length < dp[i][j].length) dp[i][j] = enc;
        }
      }
    }
  }
  return dp[0][n-1];
}

class Solution {
    public String encode(String s) {
        int n = s.length();
        String[][] dp = new String[n][n];
        for (int L = 1; L <= n; L++) {
            for (int i = 0; i + L - 1 < n; i++) {
                int j = i + L - 1;
                String sub = s.substring(i, j + 1);
                dp[i][j] = sub;
                if (L > 4) {
                    for (int k = i; k < j; k++)
                        if (dp[i][k].length() + dp[k+1][j].length() < dp[i][j].length())
                            dp[i][j] = dp[i][k] + dp[k+1][j];
                    int idx = (sub + sub).indexOf(sub, 1);
                    if (idx < L) {
                        int times = L / idx;
                        String enc = times + "[" + dp[i][i+idx-1] + "]";
                        if (enc.length() < dp[i][j].length()) dp[i][j] = enc;
                    }
                }
            }
        }
        return dp[0][n-1];
    }
}

string encode(string s) {
    int n = s.size();
    vector> dp(n, vector(n, ""));
    for (int L = 1; L <= n; L++) {
        for (int i = 0; i + L - 1 < n; i++) {
            int j = i + L - 1;
            string sub = s.substr(i, L);
            dp[i][j] = sub;
            if (L > 4) {
                for (int k = i; k < j; k++)
                    if (dp[i][k].size() + dp[k+1][j].size() < dp[i][j].size())
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                int idx = (sub + sub).find(sub, 1);
                if (idx < L) {
                    int times = L / idx;
                    string enc = to_string(times) + "[" + dp[i][i+idx-1] + "]";
                    if (enc.size() < dp[i][j].size()) dp[i][j] = enc;
                }
            }
        }
    }
    return dp[0][n-1];
}

Explanation

We want the shortest encoding of a string, where k[part] means part repeated k times. The natural approach is interval (range) DP: solve the best encoding for every substring, building from short pieces up to the whole string.

Here dp[i][j] holds the shortest encoding of the substring s[i..j]. We start each one as the raw substring itself, then try to beat it. There is no point compressing very short pieces (4 chars or fewer), since k[...] wrappers add overhead, so the work only kicks in for longer ranges.

For each range we try two ideas. First, split it at every point k and concatenate the best encodings of the two halves. Second, detect a repeat: the trick (sub + sub).indexOf(sub, 1) finds the smallest repeating block length; if the block tiles the whole range, we encode it as times[block] using the already-computed best encoding of that block.

Example: s = "aaaaaaaaaa" (ten a's). The repetition test finds a block "a" repeating 10 times, so the encoding "10[a]" (5 chars) beats the raw 10-char string.

We consider every substring and every split point inside it, which makes the work cubic in the string length, with the table taking quadratic space.

Time: O(n³) Space: O(n²)