1147. Longest Chunked Palindrome Decomposition

You are given a string text. You should split it to k substrings (subtext1, subtext2, ..., subtextk) such that:

  • subtexti is a non-empty string.
  • The concatenation of all the substrings is equal to text (i.e., subtext1 + subtext2 + ... + subtextk == text).
  • subtexti == subtextk - i + 1 for all valid values of i (i.e., 1 <= i <= k).

Return the largest possible value of k.

 

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

 

Constraints:

  • 1 <= text.length <= 1000
  • text consists only of lowercase English characters.

Rust Solution

struct Solution;

impl Solution {
    fn longest_decomposition(text: String) -> i32 {
        Self::greedy(&text)
    }

    fn greedy(s: &str) -> i32 {
        let n = s.len();
        if n == 0 {
            return 0;
        }
        for i in 1..=n / 2 {
            if s[0..i] == s[n - i..] {
                return 2 + Self::greedy(&s[i..n - i]);
            }
        }
        1
    }
}

#[test]
fn test() {
    let text = "ghiabcdefhelloadamhelloabcdefghi".to_string();
    let res = 7;
    assert_eq!(Solution::longest_decomposition(text), res);
    let text = "merchant".to_string();
    let res = 1;
    assert_eq!(Solution::longest_decomposition(text), res);
    let text = "antaprezatepzapreanta".to_string();
    let res = 11;
    assert_eq!(Solution::longest_decomposition(text), res);
    let text = "aaa".to_string();
    let res = 3;
    assert_eq!(Solution::longest_decomposition(text), res);
    let text = "elvtoelvto".to_string();
    let res = 2;
    assert_eq!(Solution::longest_decomposition(text), res);
}

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