• Time:O(n^4)
• Space:O(n^3)

## C++

``````class Solution {
public:
string encode(string s) {
const int n = s.length();
// dp[i][j] := shortest encoded string of s[i..j]
dp.resize(n, vector<string>(n));
return encode(s, 0, n - 1);
}

private:
vector<vector<string>> dp;

string encode(const string& s, int i, int j) {
if (!dp[i][j].empty())
return dp[i][j];

const string& curr = s.substr(i, j - i + 1);
dp[i][j] = curr;

if (dp[i][j].length() < 5)
return dp[i][j];

// try all possible partitions
for (int k = i; k < j; ++k) {
const string& l = encode(s, i, k);
const string& r = encode(s, k + 1, j);
if (l.length() + r.length() < dp[i][j].length())
dp[i][j] = l + r;
}

// try to compress the string
// e.g. s = aabaabaab -> 3[aab]
for (int k = i; k <= j; ++k) {
const string& pattern = s.substr(i, k - i + 1);
if (curr.length() % pattern.length() == 0 &&
regex_replace(curr, regex(pattern), "").empty()) {
const string& candidate = to_string(curr.length() / pattern.length()) +
'[' + encode(s, i, k) + ']';
if (candidate.length() < dp[i][j].length())
dp[i][j] = candidate;
}
}

return dp[i][j];
}
};
``````

## JAVA

``````class Solution {
public String encode(String s) {
final int n = s.length();
// dp[i][j] := shortest encoded String of s[i..j]
dp = new String[n][n];
return encode(s, 0, n - 1);
}

private String[][] dp;

private String encode(final String s, int i, int j) {
if (dp[i][j] != null)
return dp[i][j];

final String curr = s.substring(i, j + 1);
dp[i][j] = curr;

if (dp[i][j].length() < 5)
return dp[i][j];

// try all possible partitions
for (int k = i; k < j; ++k) {
final String l = encode(s, i, k);
final String r = encode(s, k + 1, j);
if (l.length() + r.length() < dp[i][j].length())
dp[i][j] = l + r;
}

// try to compress theString
// e.g. s = aabaabaab -> 3[aab]
for (int k = i; k <= j; ++k) {
final String pattern = s.substring(i, k + 1);
if (curr.length() % pattern.length() == 0 && curr.replaceAll(pattern, "").isEmpty()) {
final String candidate =
String.valueOf(curr.length() / pattern.length()) + "[" + encode(s, i, k) + "]";
if (candidate.length() < dp[i][j].length())
dp[i][j] = candidate;
}
}

return dp[i][j];
}
}
``````

• Time:O(n^4)
• Space:O(n^3)

## C++

``````class Solution {
public:
string encode(string s) {
const int n = s.length();
// dp[i][j] := shortest encoded string of s[i..j]
vector<vector<string>> dp(n, vector<string>(n));

for (int d = 0; d < n; ++d) {
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
const string& curr = s.substr(i, j - i + 1);
dp[i][j] = curr;

if (dp[i][j].length() < 5)
continue;

// try all possible partitions
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];

// try to compress theString
// e.g. s = aabaabaab -> 3[aab]
for (int k = i; k <= j; ++k) {
const string& pattern = s.substr(i, k - i + 1);
if (curr.length() % pattern.length() == 0 &&
regex_replace(curr, regex(pattern), "").empty()) {
const string& candidate =
to_string(curr.length() / pattern.length()) + '[' + dp[i][k] +
']';
if (candidate.length() < dp[i][j].length())
dp[i][j] = candidate;
}
}
}
}

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

## JAVA

``````class Solution {
public String encode(String s) {
final int n = s.length();
// dp[i][j] := shortest encoded String of s[i..j]
String[][] dp = new String[n][n];

for (int d = 0; d < n; ++d) {
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
final String curr = s.substring(i, j + 1);
dp[i][j] = curr;

if (dp[i][j].length() < 5)
continue;

// try all possible partitions
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];

// try to compress theString
// e.g. s = aabaabaab -> 3[aab]
for (int k = i; k <= j; ++k) {
final String pattern = s.substring(i, k + 1);
if (curr.length() % pattern.length() == 0 && curr.replaceAll(pattern, "").isEmpty()) {
final String candidate =
String.valueOf(curr.length() / pattern.length()) + "[" + dp[i][k] + "]";
if (candidate.length() < dp[i][j].length())
dp[i][j] = candidate;
}
}
}
}

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