## 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.
2. 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.

## Rust Solution

``````struct Solution;

use std::collections::HashMap;

impl Solution {
fn encode(s: String) -> String {
let mut memo: HashMap<String, String> = HashMap::new();
Self::dp(s, &mut memo)
}

fn dp(s: String, memo: &mut HashMap<String, String>) -> String {
if let Some(res) = memo.get(&s) {
return res.to_string();
}
let n = s.len();
let mut res = s.to_string();
for i in 1..n {
if n % i == 0 {
let k = n / i;
if (0..k).all(|j| s[0..i] == s[j * i..(j + 1) * i]) {
let t = format!("{}[{}]", k, Self::dp(s[0..i].to_string(), memo));
if t.len() < res.len() {
res = t;
}
}
}
}
for i in 1..n {
let t = format!(
"{}{}",
Self::dp(s[0..i].to_string(), memo),
Self::dp(s[i..].to_string(), memo)
);
if t.len() < res.len() {
res = t;
}
}
memo.insert(s, res.to_string());
res
}
}

#[test]
fn test() {
let s = "aaa".to_string();
let res = "aaa".to_string();
assert_eq!(Solution::encode(s), res);
let s = "aaaaa".to_string();
let res = "5[a]".to_string();
assert_eq!(Solution::encode(s), res);
let s = "aabcaabcd".to_string();
let res = "2[aabc]d".to_string();
assert_eq!(Solution::encode(s), res);
let s = "abbbabbbcabbbabbbc".to_string();
let res = "2[2[abbb]c]".to_string();
assert_eq!(Solution::encode(s), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.