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.

471. Encode String with Shortest Length
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);
}