<p>Given a string <code>s</code>, return <code>true</code> <em>if it is possible to split the string</em> <code>s</code> <em>into three <strong>non-empty</strong> palindromic substrings. Otherwise, return </em><code>false</code>.​​​​​</p>

<p>A string is said to be palindrome if it the same string when reversed.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abcbdd&quot;
<strong>Output:</strong> true
<strong>Explanation: </strong>&quot;abcbdd&quot; = &quot;a&quot; + &quot;bcb&quot; + &quot;dd&quot;, and all three substrings are palindromes.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;bcbddxy&quot;
<strong>Output:</strong> false
<strong>Explanation: </strong>s cannot be split into 3 palindromes.
</pre>

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

<ul>
	<li><code>3 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code>​​​​​​ consists only of lowercase English letters.</li>
</ul>

class Solution {
public:

 int solve(int index,int n,vector<vector<int>>&dp,vector<vector<int>>&dpp,int k)
 {
   if(index>n)
   {
       if(k==3)
       {
           return 1;
       }
         return 0;
   }

   int i;
   int count=0;

   if(dp[index][k]!=-1)
   {
       return dp[index][k];
   }
//dp[index][indices]=1
   // l, indices=for l+1,l+2,l+3,...n
  for(i=index;i<=n;i++)
  { 
    if(dpp[index][i]==1&&(k+1)<=3)
    {
         count=count|solve(i+1,n,dp,dpp,k+1);
    }
  }

   
    return dp[index][k]=count;
 } 
    bool checkPartitioning(string s) {
        
       int n=s.size();
       int i;

      vector<vector<int>>dp(n+1,vector<int>(4,-1));
      vector<vector<int>>dpp(n+1,vector<int>(n+1,0));
       //l-1 ,r-1,i
       int l,r;
       for(i=0;i<n;i++)
       {
      l=i-1;
      r=i+1;
     dpp[i][i]=1;
     while(l>=0&&r<=n-1)
     {
          if(s[l]==s[r])
          {
             dpp[l][r]=1;
          }
          else{
              break;
          }
         
         l=l-1;
         r=r+1;
     }
       
       }
// even length 

  //s[i-1]s[i]s[i+1]
//s[i]==s[i+1] -> s[i-1] and s[i+2]
for(i=0;i<n;i++)
{
      l=i;
      r=i+1;
      while(l>=0&&r<=n-1)
      {
          if(s[l]==s[r])
          {
             dpp[l][r]=1;
          }
          else{
              break;
          }
         
         l=l-1;
         r=r+1;
      }
}
// time complexity will be O(n*n*3)== O(n*n)
//and space complxeity  =O(n*n)+O(n*n)=O(n*n)

  int d=solve(0,n-1,dp,dpp,0);

  return d;

    }
};
131838