0471. Encode String with Shortest Length

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

Description

Given a string s, encode the string such that its encoded length is the shortest.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. k should be a positive integer.

If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them.

Example 1:

**Input:** s = "aaa"
**Output:** "aaa"
**Explanation:** There is no way to encode it such that it is shorter than the input string, so we do not encode it.

Example 2:

**Input:** s = "aaaaa"
**Output:** "5[a]"
**Explanation:** "5[a]" is shorter than "aaaaa" by 1 character.

Example 3:

**Input:** s = "aaaaaaaaaa"
**Output:** "10[a]"
**Explanation:** "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".

Example 4:

**Input:** s = "aabcaabcd"
**Output:** "2[aabc]d"
**Explanation:** "aabc" occurs twice, so one answer can be "2[aabc]d".

Example 5:

**Input:** s = "abbbabbbcabbbabbbc"
**Output:** "2[2[abbb]c]"
**Explanation:** "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".

Constraints:

• 1 <= s.length <= 150

• s consists of only lowercase English letters.

ac

class Solution {
    public String encode(String s) {
        // edge cases
        if (s == null || s.length() <= 4) return s;

        int n = s.length();
        String[][] dp = new String[n][n];

        for (int len = 0; len < n; len++) {
            for (int l = 0; l + len < n; l++) {
                int r = l + len;
                String subs = s.substring(l, r+1);
                dp[l][r] = subs;
                // length <= 4, no encode
                if (len < 4) {
                    continue;
                }
                // length > 4, left and right
                for (int m = l; m < r; m++) {
                    if(dp[l][m].length() + dp[m+1][r].length() < dp[l][r].length()) {
                        dp[l][r] = dp[l][m] + dp[m+1][r];
                    }
                }
                // itself
                for (int m = 0; m < subs.length(); m++) {
                    String repeat = subs.substring(0, m+1);
                    if(repeat != null
                        && subs.length() % repeat.length() == 0 // s[l,r] maybe comprised of multiple s[l,m]
                        && subs.replaceAll(repeat, "").length() == 0 // s[l,r] is comprised of multiple s[l,m]
                        ) {
                        int freq = subs.length() / repeat.length();
                        String candidate = "" + freq + "[" + dp[l][l+m] + "]";
                        if (candidate.length() < dp[l][r].length()) {
                            dp[l][r] = candidate;
                        }
                    }
                }
            }
        }

        return dp[0][n-1];
    }
}

/*
dp, length from 1 to all: check left/right/itself, store shortes one
*/