SDE-Challenge/Count-Distinct-Palindromic-Subsequences.cpp at main · looneyd-rohit/SDE-Challenge · GitHub

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
class Solution
{
public:
    unsigned long long solve(int i, int j, int mod, string &s, vector<int> &next, vector<int> &prev, vector<vector<unsigned long long>> &dp)
    {
        // base cases
        if (i == j)
        {
            // string of length = 1
            return 1;
        }
        if (i == j - 1)
        {
            // string of length = 2
            return 2;
        }
        if (i > j)
        {
            return 0;
        }

        // dp check
        if (dp[i][j] != 0)
            return dp[i][j];

        // match found
        if (s[i] == s[j])
        {
            int n = next[i], p = prev[j];
            if (n > p)
            {
                // no elements in between
                return dp[i][j] = (2 * solve(i + 1, j - 1, mod, s, next, prev, dp) % mod + 2) % mod;
            }
            else if (n == p)
            {
                // one element in between
                return dp[i][j] = (2 * solve(i + 1, j - 1, mod, s, next, prev, dp) % mod + 1) % mod;
            }
            else
            {
                // two or more elements in between
                return dp[i][j] = (((2 * solve(i + 1, j - 1, mod, s, next, prev, dp) % mod - solve(n + 1, p - 1, mod, s, next, prev, dp) + mod) % mod) + mod) % mod;
            }
        }
        else
        {
            // (i, j) = (i+1, j) + (i, j-1) - (i+1, j-1)
            return dp[i][j] = ((((solve(i + 1, j, mod, s, next, prev, dp) + solve(i, j - 1, mod, s, next, prev, dp)) % mod - solve(i + 1, j - 1, mod, s, next, prev, dp) + mod) % mod) + mod) % mod;
        }
    }
    int countPalindromicSubsequences(string s)
    {
        int n = s.length();
        int mod = 1e9 + 7;
        vector<int> next(n, -1), prev(n, -1);
        unordered_map<char, int> umap;
        vector<int> hash(26, -1);
        for (int i = 0; i < n; i++)
        {
            char ch = s[i];
            if (umap.find(ch) != umap.end())
            {
                prev[i] = umap[ch];
            }
            else
            {
                prev[i] = -1;
            }
            umap[ch] = i;
        }
        umap.clear();
        for (int i = n - 1; i >= 0; i--)
        {
            char ch = s[i];
            if (umap.find(ch) != umap.end())
            {
                next[i] = umap[ch];
            }
            else
            {
                next[i] = -1;
            }
            umap[ch] = i;
        }
        // memoization:
        // vector<vector<unsigned long long>> dp(n, vector<unsigned long long>(n, 0));
        // return solve(0, n-1, mod, s, next, prev, dp);

        // tabulation:
        vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(n + 1, 0));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j <= n - 1; j++)
            {
                if (i == j)
                {
                    dp[i][j] = 1;
                    continue;
                }
                if (i == j - 1)
                {
                    dp[i][j] = 2;
                    continue;
                }
                if (i > j)
                {
                    continue;
                }
                // match found
                if (s[i] == s[j])
                {
                    int n = next[i], p = prev[j];
                    if (n > p)
                    {
                        // no elements in between
                        dp[i][j] = (2 * dp[i + 1][j - 1] % mod + 2) % mod;
                    }
                    else if (n == p)
                    {
                        // one element in between
                        dp[i][j] = (2 * dp[i + 1][j - 1] % mod + 1) % mod;
                    }
                    else
                    {
                        // two or more elements in between
                        dp[i][j] = (((2 * dp[i + 1][j - 1] % mod - dp[n + 1][p - 1] + mod) % mod) + mod) % mod;
                    }
                }
                else
                {
                    // (i, j) = (i+1, j) + (i, j-1) - (i+1, j-1)
                    dp[i][j] = ((((dp[i + 1][j] + dp[i][j - 1]) % mod - dp[i + 1][j - 1] + mod) % mod) + mod) % mod;
                }
            }
        }
        return dp[0][n - 1];
    }
};