<p>Given a string s, return <em>the number of different non-empty palindromic subsequences in</em> <code>s</code>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>A subsequence of a string is obtained by deleting zero or more characters from the string.</p>

<p>A sequence is palindromic if it is equal to the sequence reversed.</p>

<p>Two sequences <code>a<sub>1</sub>, a<sub>2</sub>, ...</code> and <code>b<sub>1</sub>, b<sub>2</sub>, ...</code> are different if there is some <code>i</code> for which <code>a<sub>i</sub> != b<sub>i</sub></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bccb&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> The 6 different non-empty palindromic subsequences are &#39;b&#39;, &#39;c&#39;, &#39;bb&#39;, &#39;cc&#39;, &#39;bcb&#39;, &#39;bccb&#39;.
Note that &#39;bcb&#39; is counted only once, even though it occurs twice.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba&quot;
<strong>Output:</strong> 104860361
<strong>Explanation:</strong> There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10<sup>9</sup> + 7.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s[i]</code> is either <code>&#39;a&#39;</code>, <code>&#39;b&#39;</code>, <code>&#39;c&#39;</code>, or <code>&#39;d&#39;</code>.</li>
</ul>

class Solution:
    # what is the range of values len(s) can take on? [1, 1000]
    # what is the range of values s[i] can take on? {a,b,c,d}
    # can s be a null reference? no
    # we are returning a count integer!
    # is the answer unique? yes
    # is the answer >= 0? yes

    # idea 0
    # brute force
    # use a hashset to store all palindromes found
    # use a dfs + backtracking recursive helper method
    #   to form all subsequences of s and filter out the non-palindromic subsequences
    #   add the palindromic subsequences to the hashset
    # return the size of the hashset

    # idea 1
    # dynamic programming to count the number of something
    # create hashset out of characters in s
    # set ans to size of hashset at first which is <= 4
    # o: dp(i,j) = number of palindromic subsequences in s[i:j]
    # b: dp(i,i) = 0
    #    palindromic(i,j) = returns true iff s[i:j] is palindromic
    #       ^^^ use a memoized isPalindrome(i,j) helper method
    # r: dp(i,j) = 
    #     = dp(i+1,j-1)
    #       + dp(i,j-1)
    #       + dp(i+1,j)
    #       + (isPalindrome(i,j))
    # a: dp(0,len(s))
    # o: ??
    # pseudocode
    # p_cache = {}
    # def isPalindrome(i,j):
    #    if (i,j) in p_cache:
    #       return p_cache[(i,j)]
    #    res = True
    #    while i <= j:
    #       if s[i] !=  s[j]:
    #           res = False
    #           break
    #       if (i,j) in p_cache:
    #           res = p_cache[(i,j)]
    #           break
    #       i+=1
    #       j-=1
    #    # at this point, i > j
    #    p_cache[(i,j)] = res
    #    return res
    # numSingles = len(set([c for c in s]))
    # dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
    # for endIdx in range(len(s)):
    #    for startIdx in range(endIdx+1):
    # r: dp(i,j) = 
    #     = dp(i+1,j-1)
    #       + dp(i,j-1)
    #       + dp(i+1,j)
    #       + (isPalindrome(i,j))
    # return dp[0][len(s)] + numSingles

    def countPalindromicSubsequences(self, s: str) -> int:
        # implement idea 1 (bottom up DP + tabulation) <<< doesn't work
        # p_cache = {}
        # def isPalindrome(i,j):
        #     if (i,j) in p_cache:
        #         return p_cache[(i,j)]
        #     res = True
        #     while i <= j:
        #         if s[i] !=  s[j]:
        #             res = False
        #             break
        #         if (i,j) in p_cache:
        #             res = p_cache[(i,j)]
        #             break
        #         i+=1
        #         j-=1
        #     # at this point, i > j
        #     p_cache[(i,j)] = res
        #     return res
        # numSingles = len(set([c for c in s]))
        # dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
        # for endIdx in range(len(s)):
        #     for startIdx in range(endIdx):
        #         if startIdx == endIdx:
        #             continue
        #         dp[startIdx][endIdx] = (
        #             dp[startIdx+1][endIdx-1] +
        #             dp[startIdx][endIdx-1] +
        #             # dp[startIdx+1][endIdx] +
        #             isPalindrome(startIdx,endIdx)
        #         )
        # return dp[0][len(s)-1] + numSingles

        # Fellow LeetCodian top down DP solution #1 from
        #    https://leetcode.com/problems/count-different-palindromic-subsequences/solutions/4019256/python-3-7-lines-dp-t-s-96-51
        dp_cache = {}
        def dp(le,ri):
            if (le,ri) in dp_cache:
                return dp_cache[(le,ri)]
            res = 0
            for c in 'abcd': # O(4) = O(1) time
                le_ = s.find(c,le,ri) # <<< search for c in s[le:ri] starting at le (O(N) time)
                ri_ = s.rfind(c,le,ri) # <<< search for c in s[le:ri] starting at ri-1 going back (O(N) time)
                if le_ != -1:
                    # we found c in s[le:ri]
                    if le_==ri_:
                        # but c is unique in s[le:ri],
                        #   so add on a single 1
                        #   for subsequence 'c'
                        res+=1
                    else: # le_ != ri_
                        # we found two distinct instances
                        #   of c in s[le:ri],
                        #   add on two for subsequence 'c'
                        #   and subsequence 'cc', AND
                        #   add on however many subsequences
                        #   in s[le_+1:ri_]
                        res+=2+dp(le_+1,ri_)
            dp_cache[(le,ri)]=res
            return res
        return dp(0,len(s)) % ((10**9)+7)
        # Time = O(4*2*N) = O(N) for the .find() method
        #     and the .rfind() method in the dp() helper method
        #     that runs together four times
        # Memory = O(N^2 + N) = O(N^2) for the dp cache
        #     the max recursive call stack size caused by the
        #     dp() helper method

                
        
87121