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]".
Constraints:
1 <= s.length <= 150s consists of only lowercase English letters.
Solutions
Solution 1
PythonJavaC++GoTypeScript
class Solution:
def encode(self, s: str) -> str:
def g(i: int, j: int) -> str:
t = s[i : j + 1]
if len(t) < 5:
return t
k = (t + t).index(t, 1)
if k < len(t):
cnt = len(t) // k
return f"{cnt}[{f[i][i + k - 1]}]"
return t
n = len(s)
f = [[None] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
f[i][j] = g(i, j)
if j - i + 1 > 4:
for k in range(i, j):
t = f[i][k] + f[k + 1][j]
if len(f[i][j]) > len(t):
f[i][j] = t
return f[0][-1](code-box)
class Solution {
private String s;
private String[][] f;
public String encode(String s) {
this.s = s;
int n = s.length();
f = new String[n][n];
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
f[i][j] = g(i, j);
if (j - i + 1 > 4) {
for (int k = i; k < j; ++k) {
String t = f[i][k] + f[k + 1][j];
if (f[i][j].length() > t.length()) {
f[i][j] = t;
}
}
}
}
}
return f[0][n - 1];
}
private String g(int i, int j) {
String t = s.substring(i, j + 1);
if (t.length() < 5) {
return t;
}
int k = (t + t).indexOf(t, 1);
if (k < t.length()) {
int cnt = t.length() / k;
return String.format("%d[%s]", cnt, f[i][i + k - 1]);
}
return t;
}
}(code-box)
class Solution {
public:
string encode(string s) {
int n = s.size();
vector<vector<string>> f(n, vector<string>(n));
auto g = [&](int i, int j) {
string t = s.substr(i, j - i + 1);
if (t.size() < 5) {
return t;
}
int k = (t + t).find(t, 1);
if (k < t.size()) {
int cnt = t.size() / k;
return to_string(cnt) + "[" + f[i][i + k - 1] + "]";
}
return t;
};
for (int i = n - 1; ~i; --i) {
for (int j = i; j < n; ++j) {
f[i][j] = g(i, j);
if (j - i + 1 > 4) {
for (int k = i; k < j; ++k) {
string t = f[i][k] + f[k + 1][j];
if (t.size() < f[i][j].size()) {
f[i][j] = t;
}
}
}
}
}
return f[0][n - 1];
}
};(code-box)
func encode(s string) string {
n := len(s)
f := make([][]string, n)
for i := range f {
f[i] = make([]string, n)
}
g := func(i, j int) string {
t := s[i : j+1]
if len(t) < 5 {
return t
}
k := strings.Index((t + t)[1:], t) + 1
if k < len(t) {
cnt := len(t) / k
return strconv.Itoa(cnt) + "[" + f[i][i+k-1] + "]"
}
return t
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
f[i][j] = g(i, j)
if j-i+1 > 4 {
for k := i; k < j; k++ {
t := f[i][k] + f[k+1][j]
if len(t) < len(f[i][j]) {
f[i][j] = t
}
}
}
}
}
return f[0][n-1]
}(code-box)
function encode(s: string): string {
const n = s.length;
const f: string[][] = new Array(n).fill(0).map(() => new Array(n).fill(''));
const g = (i: number, j: number): string => {
const t = s.slice(i, j + 1);
if (t.length < 5) {
return t;
}
const k = t.repeat(2).indexOf(t, 1);
if (k < t.length) {
const cnt = Math.floor(t.length / k);
return cnt + '[' + f[i][i + k - 1] + ']';
}
return t;
};
for (let i = n - 1; i >= 0; --i) {
for (let j = i; j < n; ++j) {
f[i][j] = g(i, j);
if (j - i + 1 > 4) {
for (let k = i; k < j; ++k) {
const t = f[i][k] + f[k + 1][j];
if (t.length < f[i][j].length) {
f[i][j] = t;
}
}
}
}
}
return f[0][n - 1];
}(code-box)
