Solution by imsure


  • 1
    I

    Approach #1 Dynamic Programming [Accepted]

    Intuition and Algorithm

    Let dp[x][i][j] be the answer for the substring S[i...j] where
    S[i] == S[j] == 'a'+x. Note that since we only have 4 characters a, b, c, d, thus 0 <= x < 4. The DP formula goes as follows:

    • If S[i] != 'a'+x, then dp[x][i][j] = dp[x][i+1][j], note that
      here we leave the first character S[i] in the window out due to
      our definition of dp[x][i][j].

    • If S[j] != 'a'+x, then dp[x][i][j] = dp[x][i][j-1], leaving the
      last character S[j] out.

    • If S[i] == S[j] == 'a'+x, then dp[x][i][j] = 2 + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]. When the first and last characters are the same, we
      need to count all the distinct palindromes (for each of a,b,c,d) within
      the sub-window S[i+1][j-1] plus the 2 palindromes contributed by
      the first and last characters.

    Let n be the length of the input string S, The final answer would
    be dp[0][0][n-1] + dp[1][0][n-1] + dp[2][0][n-1] + dp[3][0][n-1]
    mod 1000000007.

    C++

    class Solution {
    public:
      int countPalindromicSubsequences(string S) {
        int n = S.size();
        int mod = 1000000007;
        auto dp_ptr = new vector<vector<vector<int>>>(4, vector<vector<int>>(n, vector<int>(n)));
        auto& dp = *dp_ptr;
    
        for (int i = n-1; i >= 0; --i) {
          for (int j = i; j < n; ++j) {
            for (int k = 0; k < 4; ++k) {
              char c = 'a' + k;
              if (j == i) {
                if (S[i] == c) dp[k][i][j] = 1;
                else dp[k][i][j] = 0;
              } else { // j > i
                if (S[i] != c) dp[k][i][j] = dp[k][i+1][j];
                else if (S[j] != c) dp[k][i][j] = dp[k][i][j-1];
                else { // S[i] == S[j] == c
                  if (j == i+1) dp[k][i][j] = 2; // "aa" : {"a", "aa"}
                  else { // length is > 2
                    dp[k][i][j] = 2;
                    for (int m = 0; m < 4; ++m) { // count each one within subwindows [i+1][j-1]
                      dp[k][i][j] += dp[m][i+1][j-1];
                      dp[k][i][j] %= mod;
                    }
                  }
                }
              }
            }
          }
        }
    
        int ans = 0;
        for (int k = 0; k < 4; ++k) {
          ans += dp[k][0][n-1];
          ans %= mod;
        }
    
        return ans;
      }
    };
    

    Example Walkthrough

    Indeed this is a hard problem to solve and thoroughly understanding
    its solution is also challenging. Maybe the best way to understand the
    above approach is to walkthrough some simple examples to help build up
    intuitions.

    0_1511472966172_730-walkthrough.png

    Complexity Analysis

    • Time complexity : $$O(n^2)$$ where $$n$$ is the length of the input
      string $$S$$. It takes quadratic time to fill up the DP table.

    • Space complexity : $$O(n^2)$$ where $$n$$ is the length of the input
      string $$S$$. The DP table takes quadratic space.

    Note that we ignore the constant factor $$4$$ in the above analysis.

    Conclusion

    As we look back, this problem reveals a key attribute which indicates
    that dynamic programming might be a good fit: overlapping sub-problems as we recall the DP formula. By practicing more
    problems, we can build up this kind of intuition.

    Credit: the above solution is inspired by
    this post
    written by @lastico. His solution is space optimized. However, I found
    that my approach is relatively easy to understand for people who found
    this problem hard to approach.


Log in to reply
 

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