Skip to content

3504. Longest Palindrome After Substring Concatenation II 👍

  • Time: $O(|\texttt{s}||\texttt{t}|)$
  • Space: $O(|\texttt{s}||\texttt{t}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  // 3503. Longest Palindrome After Substring Concatenation I
  int longestPalindrome(string s, string t) {
    const int m = s.length();
    const int n = t.length();
    vector<int> suffix = getPalindromeLengths(s, true);
    vector<int> prefix = getPalindromeLengths(t, false);
    int ans = max(ranges::max(suffix), ranges::max(prefix));
    // dp[i][j] := the longest length of palindrome starting in s[i] and ending
    // in t[j]
    vector<vector<int>> dp(m, vector<int>(n));

    for (int i = 0; i < m; ++i)
      for (int j = n - 1; j >= 0; --j)
        if (s[i] == t[j]) {
          dp[i][j] = 2 + (i > 0 && j < n - 1 ? dp[i - 1][j + 1] : 0);
          const int extend =
              max(i + 1 < m ? suffix[i + 1] : 0, j > 0 ? prefix[j - 1] : 0);
          ans = max(ans, dp[i][j] + extend);
        }

    return ans;
  }

 private:
  vector<int> getPalindromeLengths(const string& s, bool isSuffix) {
    const int n = s.length();
    // dp[i][j] := True if s[i..j] is a palindrome
    vector<vector<bool>> dp(n, vector<bool>(n));
    // lengths[i] := length of longest palindrome in s[i..n - 1]
    vector<int> lengths(n);
    for (int i = n - 1; i >= 0; --i)
      for (int j = i; j < n; ++j)
        if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
          dp[i][j] = true;
          const int index = isSuffix ? i : j;
          lengths[index] = max(lengths[index], j - i + 1);
        }
    return lengths;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
  // 3503. Longest Palindrome After Substring Concatenation I
  public int longestPalindrome(String s, String t) {
    final int m = s.length();
    final int n = t.length();
    int[] suffix = getPalindromeLengths(s, true);
    int[] prefix = getPalindromeLengths(t, false);
    int ans = Math.max(Arrays.stream(suffix).max().getAsInt(), //
                       Arrays.stream(prefix).max().getAsInt());
    // dp[i][j] := the longest length of palindrome starting in s[i] and ending
    // in t[j]
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = n - 1; j >= 0; --j)
        if (s.charAt(i) == t.charAt(j)) {
          dp[i][j] = 2 + (i > 0 && j < n - 1 ? dp[i - 1][j + 1] : 0);
          final int extend = Math.max(i + 1 < m ? suffix[i + 1] : 0, j > 0 ? prefix[j - 1] : 0);
          ans = Math.max(ans, dp[i][j] + extend);
        }

    return ans;
  }

  private int[] getPalindromeLengths(String s, boolean isSuffix) {
    final int n = s.length();
    // dp[i][j] := True if s[i..j] is a palindrome
    boolean[][] dp = new boolean[n][n];
    // lengths[i] := length of longest palindrome in s[i..n - 1]
    int[] lengths = new int[n];
    for (int i = n - 1; i >= 0; --i)
      for (int j = i; j < n; ++j)
        if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
          dp[i][j] = true;
          final int index = isSuffix ? i : j;
          lengths[index] = Math.max(lengths[index], j - i + 1);
        }
    return lengths;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
  # 3503. Longest Palindrome After Substring Concatenation I
  def longestPalindrome(self, s: str, t: str) -> int:
    m = len(s)
    n = len(t)
    suffix = self._getPalindromeLengths(s, True)
    prefix = self._getPalindromeLengths(t, False)
    ans = max(max(suffix), max(prefix))
    # dp[i][j] := the longest length of palindrome starting in s[i] and ending
    # in t[j]
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
      for j in range(n - 1, -1, -1):
        if s[i] == t[j]:
          dp[i][j] = 2 + (dp[i - 1][j + 1] if i > 0 and j < n - 1 else 0)
          extend = max(suffix[i + 1] if i + 1 < m else 0,
                       prefix[j - 1] if j > 0 else 0)
          ans = max(ans, dp[i][j] + extend)

    return ans

  def _getPalindromeLengths(self, s: str, isSuffix: bool) -> list[int]:
    n = len(s)
    # dp[i][j] := True if s[i..j] is a palindrome
    dp = [[False] * n for _ in range(n)]
    # lengths[i] := length of longest palindrome in s[i..n - 1]
    lengths = [0] * n
    for i in range(n - 1, -1, -1):
      for j in range(i, n):
        if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
          dp[i][j] = True
          index = i if isSuffix else j
          lengths[index] = max(lengths[index], j - i + 1)
    return lengths