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.

1147. Longest Chunked Palindrome Decomposition
``````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);
}
``````