5-liner & 7-liner two versions O(N^2) clean DP (detailed explanation)


  • 3

    It is natural to solve subsequence related problems with DP because a subsequence of a substring must be a subsequence of the string itself.

    Solution 1:
    We focus on the first s[0] and last char s[n-1] of string s. The longest palindromic subsequence seq of s must be one of the two cases:

    1. s[0] == s[n-1]: seq must include s[0], s[n-1], and therefore, seq without s[0], s[n-1] must be a longest palindromic subsequence of substring s[1:n-2];
    2. s[0] != s[n-1]: seq cannot include both s[0] and s[n-1], so seq is either a palindromic subsequence of substring s[1:n-1] or s[0:n-2].

    Therefore, we have the straightforward DP recursion. Let dp[i][j] = length of longest palindromic subsequence of substring s[i:j] (i<j), then

    • dp[i][j] = s[i]==s[j]? dp[i+1][j-1]+2 : max(dp[i][j-1],dp[i+1][j]).

    Note: we must calculate dp[i][j] with smaller index difference j-i first before larger ones based on the recursion above.

        int longestPalindromeSubseq(string s) {
            int n = s.size(); vector<vector<int>> dp(n, vector<int>(n));
            for(int d = 0; d < n; d++) // d = j-i
                for(int i = 0, j = i+d; j < n; i++,j++)
                    dp[i][j] = d? s[i]==s[j]? dp[i+1][j-1]+2 : max(dp[i][j-1],dp[i+1][j]) : 1;
    
            return dp[0][n-1];
        }
    

    Solution 2:
    We focus only on the last char s[n-1] of string s. Any palindromic subsequence seq of s must be in one of the two categories:

    1. seq does not include s[n-1]: seq must be a palindromic subsequence of substring s[0,n-2];
    2. seq includes s[n-1]: we must have first char of seq s[k] = s[n-1] because of palindrome.Therefore, seq without first char s[k] and last char s[n-1] must be a palindromic subsequence of substring s[k+1,n-2].

    Therefore, we have DP recursion:

    • dp[i][j] = max(dp[i][j-1], k<j? dp[k+1][j-1]+2 : 1),
      where k = the index of first char s[j] in s[i:].
        int longestPalindromeSubseq(string s) {
          int n = s.size(); vector<unordered_map<char,int>> next(n); // next[i][c]: index of first c in s[i:]
          for (int i = n-1; i >= 0; next[i][s[i]] = i--) if (i+1<n) next[i] = next[i+1]; // O(n^2) 
            
          vector<vector<int>> dp(n,vector<int>(n)); // dp[i][j]: result for substring s[i:j]   
          for (int d = 0; d < n; ++d)               // d = j-i: O(n)
            for (int i = 0, j = i+d, k; j < n; ++i,++j) // O(n)
              dp[i][j] = max(dp[i][j-1], (k=next[i][s[j]]) < j? dp[k+1][j-1]+2 : 1);
              
          return dp[0][n-1];
        }
    

  • 0
    L

    Thanks! Very detailed explanation!


  • 0
    J

    @zzg_zzm Great solutions. However in your explanation you say:

    If s[0] == s[n-1], seq must include s[0], s[n-1]

    , but this is not immediately obvious. Consider the string bbacab where s[0] == s[n-1]. You can make seq without using s[0]. So for completeness, you need to prove that:

    When s[0] == s[n-1] then LPS(s[1:n-2]) + 2 >= LPS(s[1:n-1]).


  • 1

    @jrusev Yes, you have a good point. When s[0] == s[n-1], it is still not trivial to say longest palindrome in s[1:n-2] plus first and last chars will make the longest palindrome in entire s. The longest palindrome might use only one between first and last chars. But by the condition, I think this can be always adjusted to use both first and last chars which makes the same length of palindrome subsequence.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.