Question

1147. Longest Chunked Palindrome Decomposition

中文文档

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.

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.

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

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;
  }
}

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;
  }
};

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
}

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.

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

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;
  }
}

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;
  }
};

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
}

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

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

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];
  }
}

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;
  }
};

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
}