471. Encode String with Shortest Length

Given a non-empty string, 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.

Note:

1. k will be a positive integer and encoded string will not be empty or have extra space.

2. You may assume that the input string contains only lowercase English letters. The string's length is at most 160.

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

Example 1:

Input: "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: "aaaaa"
Output: "5[a]"
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.

Example 3:

Input: "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: "aabcaabcd"
Output: "2[aabc]d"
Explanation: "aabc" occurs twice, so one answer can be "2[aabc]d".

Example 5:

Input: "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]".

dp[i][j]代表的是string s[i...j]的encoded form。dp state transition: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])，如果長度短，就選擇長度短的存。 如果substring本身就有重複的pattern，那麼encode完之後不需要再檢查中間各個k拆開形成的兩個子字串，因為最短的可能就是找到重複的然後直接表示。

// Dynamic programming
string encode(string s) { // time: O(n^3); space: O(n^2)
    int n = s.length();
    vector<vector<string> > dp(n, vector<string>(n, "")); // dp[i][j]: the encoded form of s[i...j]
    for (int len = 1; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            string t = s.substr(i, len), replace = "";
            dp[i][j] = t;
            auto pos = (t + t).find(t, 1); // find the second occurrence position
            if (pos < t.size()) { // found repeated pattern in string itself
                replace = to_string(t.size() / pos) + "[" + dp[i][i + pos - 1] + "]";
                if (replace.size() < dp[i][j].size()) dp[i][j] = replace;
                continue; // no need to check if the length of (dp[i][k] + dp[k + 1][j]) is shorter
            }
            // Check if the length of (dp[i][k] + dp[k + 1][j]) is shorter
            // dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
            for (int k = i; k < j; ++k) {
                const string &left = dp[i][k], &right = dp[k + 1][j];
                if (left.size() + right.size() < dp[i][j].size()) {
                    dp[i][j] = left + right;
                }
            }
        }
    }
    return dp[0][n - 1];
}

394. Decode String