1147. Longest Chunked Palindrome Decomposition
You are given a string text. You should split it to k substrings $(subtext_1, subtext_2, …, subtext_k)$4 such that:
-
s
u
b
t
e
x
t
i
subtext_i
subtexti is a non-empty string. - The concatenation of all the substrings is equal to text (i.e.,
s
u
b
t
e
x
t
1
+
s
u
b
t
e
x
t
2
+
.
.
.
+
s
u
b
t
e
x
t
k
=
=
t
e
x
t
subtext_1 + subtext_2 + … + subtext_k == text
subtext1+subtext2+…+subtextk==text). -
s
u
b
t
e
x
t
i
=
=
s
u
b
t
e
x
t
k
−
i
+
1
subtext_i == subtext_{k – i + 1}
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.
From: LeetCode Link: 1147. Longest Chunked Palindrome Decomposition
Solution:
Ideas:
greedily match the shortest same prefix and suffix. Each match gives 2 chunks, except when they meet in the middle, then it gives 1.
Code:
int longestDecomposition(char* text) {
int n = strlen(text);
int l = 0, r = n – 1;
int len = 1;
int ans = 0;
while (l <= r) {
int ok = 1;
for (int i = 0; i < len; i++) {
if (text[l + i] != text[r – len + 1 + i]) {
ok = 0;
break;
}
}
if (ok) {
if (l + len – 1 < r – len + 1)
ans += 2;
else
ans += 1;
l += len;
r -= len;
len = 1;
} else {
len++;
}
}
return ans;
}
