Skip to content

3472. Longest Palindromic Subsequence After at Most K Operations 👍

Approach 1: Top-down

  • Time: $O(n^2k)$
  • Space: $O(n^2k)$
 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 {
 public:
  // Similar to 516. Longest Palindromic Subsequence
  int longestPalindromicSubsequence(string s, int k) {
    const int n = s.length();
    vector<vector<vector<int>>> mem(
        n, vector<vector<int>>(n, vector<int>(k + 1, -1)));
    return lps(s, 0, n - 1, k, mem);
  }

 private:
  // Returns the length of LPS(s[i..j]) with at most `op` operations.
  int lps(const string& s, int i, int j, int op,
          vector<vector<vector<int>>>& mem) {
    if (i > j)
      return 0;
    if (i == j)
      return 1;
    if (mem[i][j][op] != -1)
      return mem[i][j][op];
    if (s[i] == s[j])
      return mem[i][j][op] = 2 + lps(s, i + 1, j - 1, op, mem);
    mem[i][j][op] = max(lps(s, i + 1, j, op, mem), lps(s, i, j - 1, op, mem));
    const int cost = getCost(s[i], s[j]);
    if (cost <= op)
      mem[i][j][op] =
          max(mem[i][j][op], 2 + lps(s, i + 1, j - 1, op - cost, mem));
    return mem[i][j][op];
  }

  int getCost(char a, char b) {
    const int dist = abs(a - b);
    return min(dist, 26 - dist);
  }
};

 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
class Solution {
  // Similar to 516. Longest Palindromic Subsequence
  public int longestPalindromicSubsequence(String s, int k) {
    final int n = s.length();
    Integer[][][] mem = new Integer[n][n][k + 1];
    return lps(s, 0, n - 1, k, mem);
  }

  // Returns the length of LPS(s[i..j]) with at most `op` operations.
  private int lps(String s, int i, int j, int op, Integer[][][] mem) {
    if (i > j)
      return 0;
    if (i == j)
      return 1;
    if (mem[i][j][op] != null)
      return mem[i][j][op];
    if (s.charAt(i) == s.charAt(j))
      return mem[i][j][op] = 2 + lps(s, i + 1, j - 1, op, mem);
    mem[i][j][op] = Math.max(lps(s, i + 1, j, op, mem), lps(s, i, j - 1, op, mem));
    final int cost = getCost(s.charAt(i), s.charAt(j));
    if (cost <= op)
      mem[i][j][op] = Math.max(mem[i][j][op], 2 + lps(s, i + 1, j - 1, op - cost, mem));
    return mem[i][j][op];
  }

  private int getCost(char a, char b) {
    final int dist = Math.abs(a - b);
    return Math.min(dist, 26 - dist);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  # Similar to 516. Longest Palindromic Subsequence
  def longestPalindromicSubsequence(self, s: str, k: int) -> int:
    @functools.lru_cache(None)
    def dp(i: int, j: int, op: int) -> int:
      """Returns the length of LPS(s[i..j]) with at most `op` operations."""
      if i > j:
        return 0
      if i == j:
        return 1
      if s[i] == s[j]:
        return 2 + dp(i + 1, j - 1, op)
      res = max(dp(i + 1, j, op), dp(i, j - 1, op))
      cost = self._getCost(s[i], s[j])
      if cost <= op:
        res = max(res, 2 + dp(i + 1, j - 1, op - cost))
      return res

    return dp(0, len(s) - 1, k)

  def _getCost(self, a: str, b: str) -> int:
    dist = abs(ord(a) - ord(b))
    return min(dist, 26 - dist)

Approach 2: Bottom-up

  • Time: $O(n^2k)$
  • Space: $O(n^2k)$
 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
class Solution {
 public:
  // Similar to 516. Longest Palindromic Subsequence
  int longestPalindromicSubsequence(string s, int k) {
    const int n = s.length();
    // dp[i][j][op] := the length of LPS(s[i..j]) with at most `op` operations
    vector<vector<vector<int>>> dp(n,
                                   vector<vector<int>>(n, vector<int>(k + 1)));

    for (int i = 0; i < n; ++i)
      for (int op = 0; op <= k; ++op)
        dp[i][i][op] = 1;

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        for (int op = 0; op <= k; ++op) {
          if (s[i] == s[j]) {
            dp[i][j][op] = 2 + dp[i + 1][j - 1][op];
          } else {
            dp[i][j][op] = max(dp[i + 1][j][op], dp[i][j - 1][op]);
            const int cost = getCost(s[i], s[j]);
            if (cost <= op)
              dp[i][j][op] = max(dp[i][j][op], 2 + dp[i + 1][j - 1][op - cost]);
          }
        }
      }

    return dp[0][n - 1][k];
  }

 private:
  int getCost(char a, char b) {
    const int dist = abs(a - b);
    return min(dist, 26 - dist);
  }
};

 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
class Solution {
  // Similar to 516. Longest Palindromic Subsequence
  public int longestPalindromicSubsequence(String s, int k) {
    final int n = s.length();
    // dp[i][j][op] := the length of LPS(s[i..j]) with at most `op` operations
    int[][][] dp = new int[n][n][k + 1];

    for (int i = 0; i < n; ++i)
      for (int op = 0; op <= k; ++op)
        dp[i][i][op] = 1;

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        for (int op = 0; op <= k; ++op) {
          if (s.charAt(i) == s.charAt(j)) {
            dp[i][j][op] = 2 + dp[i + 1][j - 1][op];
          } else {
            dp[i][j][op] = Math.max(dp[i + 1][j][op], dp[i][j - 1][op]);
            final int cost = getCost(s.charAt(i), s.charAt(j));
            if (cost <= op)
              dp[i][j][op] = Math.max(dp[i][j][op], 2 + dp[i + 1][j - 1][op - cost]);
          }
        }
      }

    return dp[0][n - 1][k];
  }

  private int getCost(char a, char b) {
    final int dist = Math.abs(a - b);
    return Math.min(dist, 26 - dist);
  }
}

 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:
  # Similar to 516. Longest Palindromic Subsequence
  def longestPalindromicSubsequence(self, s: str, k: int) -> int:
    n = len(s)
    # dp[i][j][op] := the length of LPS(s[i..j]) with at most `op` operations
    dp = [[[0] * (k + 1) for _ in range(n)] for _ in range(n)]

    for i in range(n):
      for op in range(k + 1):
        dp[i][i][op] = 1

    for d in range(1, n):
      for i in range(n - d):
        j = i + d
        for op in range(k + 1):
          if s[i] == s[j]:
            dp[i][j][op] = 2 + dp[i + 1][j - 1][op]
          else:
            dp[i][j][op] = max(dp[i + 1][j][op], dp[i][j - 1][op])
            cost = self._getCost(s[i], s[j])
            if cost <= op:
              dp[i][j][op] = max(dp[i][j][op], 2 + dp[i + 1][j - 1][op - cost])

    return dp[0][n - 1][k]

  def _getCost(self, a: str, b: str) -> int:
    dist = abs(ord(a) - ord(b))
    return min(dist, 26 - dist)