<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 {
public:
    int countPalindromicSubsequences(string s) {
        vector<vector<int>> indices(4);  // ordered positions
        for (int i = 0; i < s.length(); i++) {
            indices[s[i] - 'a'].push_back(i);
        }
        return solve(s, 0, s.length() - 1, indices, {}) - 1;
    }

    int solve(const string& s, int start, int end, const vector<vector<int>>& indices, unordered_map<string, int>&& memo) {
        int kMod = 1e9 + 7;
        if (start > end) return 1;
        if (start == end) return 2;
        string key = to_string(start) + "#" + to_string(end);
        if (auto it = memo.find(key); it != memo.end())
            return it->second;
        vector<int> used(4);
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (used[s[i] - 'a']) continue;
            used[s[i] - 'a'] = 1;
            const vector<int>& idxs = indices[s[i] - 'a'];
            auto pos = upper_bound(idxs.begin(), idxs.end(), end);
            if (pos != idxs.begin()) {  // new pair
                int j = *(pos - 1);
                if (i >= j) continue;
                count = (count + solve(s, i + 1, j - 1, indices, move(memo))) % kMod;
            }
        }
        count = (count + accumulate(used.begin(), used.end(), 0) + 1) % kMod;
        return memo[key] = count;
    }
};
73253