title: Number of ways selecting a pair of non-overlapping substrings which are palindromes
body: <p>Given a string <code>s</code>, it is expected to find the number of ways of selecting a pair of non-overlapping substrings which are palindromes.<br>
  For example in the string <code>abcdcefdfdio</code>, one way is selecting <code>cdc</code> and <code>dfd</code>.<br>
  My approach was a dp one:  </p>
  
  <pre><code>    String s = sc.next();
      int n = s.length();
      int firstsum[] = new int[n];//firstsum[i] stores the number of palindromes in the substring (0...i)
      int[][] A = new int[n][n];//A[i][j]=1 denotes the substring (i...j) is a palindrome and =0 otherwise
      for(int i=0;i&lt;n;++i)
      {
          firstsum[i]=0;
          for(int j=i;j&lt;n;++j)
          {
              if(check(s.substring(i,j+1))==1)
              {
                  A[i][j]=1;
              }
              else
                  A[i][j]=0;
          }
      }
      for(int i=0;i&lt;n;++i)
      {
          for(int j=0;j&lt;=i;++j)
          {
              if(A[j][i]==1)
                  firstsum[i]++;
          }
          if(i&gt;0)
              firstsum[i]+=firstsum[i-1];
      }
      int cnt=0;
      for(int i=1;i&lt;n;++i)
      {
          for(int j=i;j&lt;n;++j)
              cnt+=A[i][j]*firstsum[i-1];
      }
      System.out.print(cnt);//answer
  </code></pre>
  
  <p>The <a href="https://ideone.com/d43yUu" rel="nofollow">solution</a> is working but is exceeding the time limit. Is there a better approach, in DP preferably?</p>