# Calculate the number of palindrome sub-sequence for a given string.

• Given a string s, calculate the number of palindrome sub-sequence. For example, s = "aba", there are 5 palindrome sub-sequence: "a", "a", "aa", "b", "aba". Note that two identical sub-sequences are counted separately if at least one element has different positions in s.

More example:
ccc, then the answer is 7.

``````class Solution{
public:
int getNumberOfPalindromeSubsequence(string str){
auto len = str.size();
vector<vector<int> > dp(len, vector<int>(len, 0));
for(int i = 0; i < len; i++)    dp[i][i] = 1;
for(int j = 1; j < len; j++){
for(int i =0; i + j < len; i++){
dp[i][i + j] = dp[i][i + j - 1] + dp[i + 1][i + j] - dp[i + 1][i + j - 1];
if(str[i] == str[i + j]){
dp[i][i + j] += 1 + dp[i + 1][i + j - 1];
}
}
}

return dp[0][len - 1];
}
};
``````

My tests:

``````Solution s;
assert(s.getNumberOfPalindromeSubsequence("aba") == 5);
assert(s.getNumberOfPalindromeSubsequence("12111112351121") == 1333);
assert(s.getNumberOfPalindromeSubsequence("ccccccc") == 127);
return 0;``````

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