Return the largest possible `k`

such that there exists `a_1, a_2, ..., a_k`

such that:

- Each
`a_i`

is a non-empty string; - Their concatenation
`a_1 + a_2 + ... + a_k`

is equal to`text`

; - For all
`1 <= i <= k`

,`a_i = a_{k+1 - i}`

.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Example 4:**

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

**Solution: Greedy**

Break the string when the shortest palindrome is found.

prefer to use string_view

Time complexity: O(n^2)

Space complexity: O(n)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua, 0 ms, 8.7 ms class Solution { public: int longestDecomposition(string_view text) { const int n = text.length(); if (n == 0) return 0; for (int l = 1; l <= n / 2; ++l) { if (text.substr(0, l) == text.substr(n - l)) return 2 + longestDecomposition(text.substr(l, n - 2 * l)); } return 1; } }; |