Skip to content

1147. Longest Chunked Palindrome Decomposition 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int longestDecomposition(string text) {
    int count = 0;
    int l = 0;

    for (int r = 1; 2 * r <= text.length(); ++r)
      if (equal(text.begin() + l, text.begin() + r, text.end() - r)) {
        count += 2;
        l = r;
      }

    return count + (2 * l < text.length());
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int longestDecomposition(String text) {
    final int n = text.length();

    int count = 0;
    int l = 0;

    for (int r = 1; 2 * r <= n; ++r)
      if (text.substring(n - r).startsWith(text.substring(l, r))) {
        count += 2;
        l = r;
      }

    return count + (2 * l < n ? 1 : 0);
  }
}