No of distinct strings possible under a condition
12345678910111213141516171819202122232425262728293031323334353637
#include <iostream>
#include <vector>
using namespace std;
int main() {
string s;
cin>>s;
int n = s.length();
vector<vector<int>> dp(n , vector<int>(n));
for(int g=0; g<n; g++){
int i =0;
int j=i+g;
while( i < n && j < n){
if(g == 0){
dp[i][j] = 1;
}else if(g == 1){
if(s[i] == s[j]){
dp[i][j] = 2;
}
else{
dp[i][j] = 3;
}
}else{
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1] + 1;
}
i++;
j = i+g;
}
}
cout<<dp[0][n-1];
}
Cpp
INFO