471

class Solution {
private:
    vector<vector<string>> dp;
public:
    string collapse(string& s, int i, int j) {
        string temp = s.substr(i, j - i + 1);
        auto pos = (temp+temp).find(temp, 1);
        // Check if there is no suffix that is also a prefix.
        if (pos >= temp.size()) {
            return temp;
        }
        // If there exists a suffix that is also a prefix.
        return to_string(temp.size()/pos) + '['+ dp[i][i+pos-1]+']';
    }

    string encode(string s) {
        int n = s.size();
        dp = vector<vector<string>>(n, vector<string>(n, ""));
        for (int step = 1; step <= n; step++) {
            for (int i = 0; i + step - 1 < n; i++) {
                int j = i + step - 1;
                // There is no optimization.
                dp[i][j] = s.substr(i, step);
                for (int k = i; k < j; k++) {
                    auto left = dp[i][k];
                    auto right = dp[k + 1][j];
                    // If it is combination of 2 optimization.
                    if (left.size() + right.size() < dp[i][j].size()) {
                        dp[i][j] = left + right;
                    }
                }
                // If the string itself can be optimized.
                string replace = collapse(s, i, j);
                if (replace.size() < dp[i][j].size()) {
                    dp[i][j] = replace;
                }
            }
        }
        return dp[0][n - 1];
    }
};