Problem

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.

Examples

Example 1:

1
2
3
4
5

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

Example 2:

1
2
3
4
5

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

Example 3:

1
2
3
4
5

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

Solution

Method 1 – Greedy Two Pointers

Intuition

The key idea is to match the smallest possible prefix and suffix that are equal, then recursively solve the problem for the substring in between. This works because the palindrome decomposition requires mirrored chunks from both ends.

Approach

  1. Use two pointers, one starting from the left and one from the right.
  2. For each possible chunk length, compare the prefix and suffix of that length.
  3. If they match, count them as a chunk and move both pointers inward by the chunk length.
  4. Repeat until the pointers meet or cross.
  5. If there is a middle part left, count it as one chunk.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int longestDecomposition(string s) {
        int n = s.size(), ans = 0, l = 0, r = n;
        while (l < r) {
            int len = 1;
            while (l + len <= r - len && s.substr(l, len) != s.substr(r - len, len)) ++len;
            if (l + len > r - len) break;
            ans += 2;
            l += len;
            r -= len;
        }
        if (l < r) ans++;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func longestDecomposition(s string) int {
    n, ans, l, r := len(s), 0, 0, len(s)
    for l < r {
        length := 1
        for l+length <= r-length && s[l:l+length] != s[r-length:r] {
            length++
        }
        if l+length > r-length {
            break
        }
        ans += 2
        l += length
        r -= length
    }
    if l < r {
        ans++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int longestDecomposition(String s) {
        int n = s.length(), ans = 0, l = 0, r = n;
        while (l < r) {
            int len = 1;
            while (l + len <= r - len && !s.substring(l, l+len).equals(s.substring(r-len, r))) ++len;
            if (l + len > r - len) break;
            ans += 2;
            l += len;
            r -= len;
        }
        if (l < r) ans++;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun longestDecomposition(s: String): Int {
        var l = 0
        var r = s.length
        var ans = 0
        while (l < r) {
            var len = 1
            while (l + len <= r - len && s.substring(l, l+len) != s.substring(r-len, r)) len++
            if (l + len > r - len) break
            ans += 2
            l += len
            r -= len
        }
        if (l < r) ans++
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def longestDecomposition(self, s: str) -> int:
        n, ans, l, r = len(s), 0, 0, len(s)
        while l < r:
            length = 1
            while l + length <= r - length and s[l:l+length] != s[r-length:r]:
                length += 1
            if l + length > r - length:
                break
            ans += 2
            l += length
            r -= length
        if l < r:
            ans += 1
        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

impl Solution {
    pub fn longest_decomposition(s: String) -> i32 {
        let (mut l, mut r, n) = (0, s.len(), s.len());
        let s = s.as_bytes();
        let mut ans = 0;
        while l < r {
            let mut len = 1;
            while l + len <= r - len && &s[l..l+len] != &s[r-len..r] {
                len += 1;
            }
            if l + len > r - len {
                break;
            }
            ans += 2;
            l += len;
            r -= len;
        }
        if l < r {
            ans += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    longestDecomposition(s: string): number {
        let n = s.length, ans = 0, l = 0, r = n;
        while (l < r) {
            let len = 1;
            while (l + len <= r - len && s.slice(l, l+len) !== s.slice(r-len, r)) ++len;
            if (l + len > r - len) break;
            ans += 2;
            l += len;
            r -= len;
        }
        if (l < r) ans++;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), because for each chunk, substring comparison can take up to O(n) time and there can be up to n/2 chunks.
  • 🧺 Space complexity: O(1), only a constant amount of extra space is used (not counting input/output).