Description#
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)(tep)(za)(pre)(a)(nt)(a)".
Constraints:
1 <= text.length <= 1000
text
consists only of lowercase English characters.
Solutions#
Solution 1: Greedy + Two Pointers#
We can start from both ends of the string, looking for the shortest, identical, and non-overlapping prefixes and suffixes:
- If such prefixes and suffixes cannot be found, then the entire string is treated as a segmented palindrome, and the answer is incremented by $1$;
- If such prefixes and suffixes are found, then this prefix and suffix are treated as a segmented palindrome, and the answer is incremented by $2$, then continue to find the prefixes and suffixes of the remaining string.
The proof of the above greedy strategy is as follows:
Suppose there is a prefix $A_1$ and a suffix $A_2$ that meet the conditions, and there is a prefix $B_1$ and a suffix $B_4$ that meet the conditions. Since $A_1 = A_2$ and $B_1=B_4$, then $B_3=B_1=B_4=B_2$, and $C_1 = C_2$. Therefore, if we greedily split $B_1$ and $B_4$, then the remaining $C_1$ and $C_2$, and $B_2$ and $B_3$ can also be successfully split. Therefore, we should greedily choose the shortest identical prefix and suffix to split, so that in the remaining string, more segmented palindromes may be split.
![](https://spcdn.pages.dev/leetcode/problems/1147.Longest%20Chunked%20Palindrome%20Decomposition/images/demo.png)
The time complexity is $O(n^2)$, and the space complexity is $O(n)$ or $O(1)$. Here, $n$ is the length of the string.
1
2
3
4
5
6
7
8
9
| class Solution:
def longestDecomposition(self, text: str) -> int:
n = len(text)
if n < 2:
return n
for i in range(n // 2 + 1):
if text[:i] == text[-i:]:
return 2 + self.longestDecomposition(text[i:-i])
return 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int longestDecomposition(String text) {
int n = text.length();
if (n < 2) {
return n;
}
for (int i = 1; i <= n >> 1; ++i) {
if (text.substring(0, i).equals(text.substring(n - i))) {
return 2 + longestDecomposition(text.substring(i, n - i));
}
}
return 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int longestDecomposition(string text) {
int n = text.size();
if (n < 2) return n;
for (int i = 1; i <= n >> 1; ++i) {
if (text.substr(0, i) == text.substr(n - i)) {
return 2 + longestDecomposition(text.substr(i, n - i - i));
}
}
return 1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func longestDecomposition(text string) int {
n := len(text)
if n < 2 {
return n
}
for i := 1; i <= n>>1; i++ {
if text[:i] == text[n-i:] {
return 2 + longestDecomposition(text[i:n-i])
}
}
return 1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| function longestDecomposition(text: string): number {
const n: number = text.length;
if (n < 2) {
return n;
}
for (let i: number = 1; i <= n >> 1; i++) {
if (text.slice(0, i) === text.slice(n - i)) {
return 2 + longestDecomposition(text.slice(i, n - i));
}
}
return 1;
}
|
Solution 2: String Hash#
String hash is to map a string of any length to a non-negative integer, and its collision probability is almost $0$. String hash is used to calculate the hash value of a string and quickly determine whether two strings are equal.
Therefore, based on Solution 1, we can use the method of string hash to compare whether two strings are equal in $O(1)$ time.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def longestDecomposition(self, text: str) -> int:
ans = 0
i, j = 0, len(text) - 1
while i <= j:
k = 1
ok = False
while i + k - 1 < j - k + 1:
if text[i : i + k] == text[j - k + 1 : j + 1]:
ans += 2
i += k
j -= k
ok = True
break
k += 1
if not ok:
ans += 1
break
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int longestDecomposition(String text) {
int ans = 0;
for (int i = 0, j = text.length() - 1; i <= j;) {
boolean ok = false;
for (int k = 1; i + k - 1 < j - k + 1; ++k) {
if (check(text, i, j - k + 1, k)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
++ans;
break;
}
}
return ans;
}
private boolean check(String s, int i, int j, int k) {
while (k-- > 0) {
if (s.charAt(i++) != s.charAt(j++)) {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
int longestDecomposition(string text) {
int ans = 0;
auto check = [&](int i, int j, int k) -> bool {
while (k--) {
if (text[i++] != text[j++]) {
return false;
}
}
return true;
};
for (int i = 0, j = text.size() - 1; i <= j;) {
bool ok = false;
for (int k = 1; i + k - 1 < j - k + 1; ++k) {
if (check(i, j - k + 1, k)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
ans += 1;
break;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func longestDecomposition(text string) (ans int) {
for i, j := 0, len(text)-1; i <= j; {
ok := false
for k := 1; i+k-1 < j-k+1; k++ {
if text[i:i+k] == text[j-k+1:j+1] {
ans += 2
i += k
j -= k
ok = true
break
}
}
if !ok {
ans++
break
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| function longestDecomposition(text: string): number {
let ans = 0;
for (let i = 0, j = text.length - 1; i <= j; ) {
let ok = false;
for (let k = 1; i + k - 1 < j - k + 1; ++k) {
if (text.slice(i, i + k) === text.slice(j - k + 1, j + 1)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
++ans;
break;
}
}
return ans;
}
|
Solution 3#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution:
def longestDecomposition(self, text: str) -> int:
def get(l, r):
return (h[r] - h[l - 1] * p[r - l + 1]) % mod
n = len(text)
base = 131
mod = int(1e9) + 7
h = [0] * (n + 10)
p = [1] * (n + 10)
for i, c in enumerate(text):
t = ord(c) - ord('a') + 1
h[i + 1] = (h[i] * base) % mod + t
p[i + 1] = (p[i] * base) % mod
ans = 0
i, j = 0, n - 1
while i <= j:
k = 1
ok = False
while i + k - 1 < j - k + 1:
if get(i + 1, i + k) == get(j - k + 2, j + 1):
ans += 2
i += k
j -= k
ok = True
break
k += 1
if not ok:
ans += 1
break
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
private long[] h;
private long[] p;
public int longestDecomposition(String text) {
int n = text.length();
int base = 131;
h = new long[n + 10];
p = new long[n + 10];
p[0] = 1;
for (int i = 0; i < n; ++i) {
int t = text.charAt(i) - 'a' + 1;
h[i + 1] = h[i] * base + t;
p[i + 1] = p[i] * base;
}
int ans = 0;
for (int i = 0, j = n - 1; i <= j;) {
boolean ok = false;
for (int k = 1; i + k - 1 < j - k + 1; ++k) {
if (get(i + 1, i + k) == get(j - k + 2, j + 1)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
++ans;
break;
}
}
return ans;
}
private long get(int i, int j) {
return h[j] - h[i - 1] * p[j - i + 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
int longestDecomposition(string text) {
using ull = unsigned long long;
int n = text.size();
int base = 131;
ull p[n + 10];
ull h[n + 10];
p[0] = 1;
h[0] = 0;
for (int i = 0; i < n; ++i) {
int t = text[i] - 'a' + 1;
p[i + 1] = p[i] * base;
h[i + 1] = h[i] * base + t;
}
int ans = 0;
auto get = [&](int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
};
for (int i = 0, j = n - 1; i <= j;) {
bool ok = false;
for (int k = 1; i + k - 1 < j - k + 1; ++k) {
if (get(i + 1, i + k) == get(j - k + 2, j + 1)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
++ans;
break;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| func longestDecomposition(text string) (ans int) {
n := len(text)
base := 131
h := make([]int, n+10)
p := make([]int, n+10)
p[0] = 1
for i, c := range text {
t := int(c-'a') + 1
p[i+1] = p[i] * base
h[i+1] = h[i]*base + t
}
get := func(l, r int) int {
return h[r] - h[l-1]*p[r-l+1]
}
for i, j := 0, n-1; i <= j; {
ok := false
for k := 1; i+k-1 < j-k+1; k++ {
if get(i+1, i+k) == get(j-k+2, j+1) {
ans += 2
i += k
j -= k
ok = true
break
}
}
if !ok {
ans++
break
}
}
return
}
|