Skip to content

2002. Maximum Product of the Length of Two Palindromic Subsequences 👍

  • Time: $O(n \cdot 3^n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int maxProduct(string s) {
    size_t ans = 0;
    dfs(s, 0, "", "", ans);
    return ans;
  }

 private:
  void dfs(const string& s, int i, string&& s1, string&& s2, size_t& ans) {
    if (i == s.length()) {
      if (isPalindrome(s1) && isPalindrome(s2))
        ans = max(ans, s1.length() * s2.length());
      return;
    }

    s1.push_back(s[i]);
    dfs(s, i + 1, move(s1), move(s2), ans);
    s1.pop_back();

    s2.push_back(s[i]);
    dfs(s, i + 1, move(s1), move(s2), ans);
    s2.pop_back();

    dfs(s, i + 1, move(s1), move(s2), ans);
  }

  bool isPalindrome(const string& s) {
    int i = 0;
    int j = s.length() - 1;
    while (i < j) {
      if (s[i] != s[j])
        return false;
      ++i;
      --j;
    }
    return true;
  }
};

 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
class Solution {
  public int maxProduct(String s) {
    dfs(s, 0, new StringBuilder(), new StringBuilder());
    return ans;
  }

  private int ans = 0;

  private void dfs(final String s, int i, StringBuilder sb1, StringBuilder sb2) {
    if (i == s.length()) {
      if (isPalindrome(sb1) && isPalindrome(sb2))
        ans = Math.max(ans, sb1.length() * sb2.length());
      return;
    }

    final int sb1Length = sb1.length();
    dfs(s, i + 1, sb1.append(s.charAt(i)), sb2);
    sb1.setLength(sb1Length);

    final int sb2Length = sb2.length();
    dfs(s, i + 1, sb1, sb2.append(s.charAt(i)));
    sb2.setLength(sb2Length);

    dfs(s, i + 1, sb1, sb2);
  }

  private boolean isPalindrome(StringBuilder sb) {
    int i = 0;
    int j = sb.length() - 1;
    while (i < j) {
      if (sb.charAt(i) != sb.charAt(j))
        return false;
      ++i;
      --j;
    }
    return true;
  }
}

 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
class Solution:
  def maxProduct(self, s: str) -> int:
    ans = 0

    def isPalindrome(s: str) -> bool:
      i = 0
      j = len(s) - 1
      while i < j:
        if s[i] != s[j]:
          return False
        i += 1
        j -= 1
      return True

    @functools.lru_cache(None)
    def dfs(i: int, s1: str, s2: str) -> None:
      nonlocal ans
      if i == len(s):
        if isPalindrome(s1) and isPalindrome(s2):
          ans = max(ans, len(s1) * len(s2))
        return

      dfs(i + 1, s1 + s[i], s2)
      dfs(i + 1, s1, s2 + s[i])
      dfs(i + 1, s1, s2)

    dfs(0, '', '')
    return ans