LeetCode in Kotlin
1147. Longest Chunked Palindrome Decomposition
Hard
You are given a string text. You should split it to k substrings (subtext1, subtext2, ..., subtextk) such that:
subtextiis a non-empty string.- The concatenation of all the substrings is equal to
text(i.e.,subtext1 + subtext2 + ... + subtextk == text). subtexti == subtextk - i + 1for all valid values ofi(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)”.
Constraints:
1 <= text.length <= 1000textconsists only of lowercase English characters.
Solution
class Solution {
fun longestDecomposition(text: String): Int {
val n = text.length
var l = 0
var r = n - 1
var len = 1
var ans = 0
var lft: String
var rit: String
var perfectSubstring = false
while (l + len <= r - len + 1) {
lft = text.substring(l, l + len)
rit = text.substring(r - len + 1, r + 1)
if (lft == rit) {
ans += 2
if (l + len == r - len + 1) {
perfectSubstring = true
break
}
l = l + len
r = r - len
len = 1
} else {
len++
}
}
if (!perfectSubstring) {
ans++
}
return ans
}
}