title: Number of Palindromic Subsequences of length 5 in Binary String
body: <p>Given a string <code>s</code>, which consists of characters <code>&quot;0&quot;</code> and <code>&quot;1&quot;</code> only, return the number of subsequences of length 5, which are palindromes.</p>
  <p>As the number can be really big, return the answer mod(10^9 +7)</p>
  <p>Test case 1:</p>
  <pre><code>input: &quot;0100110&quot;
  
  output: 5
  
  indices(1,2,3,6,7) -&gt; &quot;01010&quot;
  
  indices(1,2,3,5,7) -&gt; &quot;01010&quot;
  
  indices(1,2,4,6,7) -&gt; &quot;01010&quot;
  
  indices(1,2,4,5,7) -&gt; &quot;01010&quot;
  
  indices(1,2,5,6,7) -&gt; &quot;01110&quot;
  
  5 mod(10^9 +7) = 5
  </code></pre>
  <p>Test case 2:</p>
  <pre><code>input: &quot;010110&quot;
  
  output: 3
  
  indices(1,2,3,4,6) -&gt; &quot;01010&quot;
  
  indices(1,2,3,5,6) -&gt; &quot;01010&quot;
  
  indices(1,2,4,5,7) -&gt; &quot;01110&quot;
  
  3 mod(10^9 +7) = 3
  </code></pre>
  <p>Test case 3</p>
  <pre><code>input: &quot;01111&quot;
  
  output: 0
  
  There is no palindromic subsequence of length 5
  </code></pre>
  <p>I have been trying to solve the challenge above in python. I tried a dynamic programming approach for counting palindromic subsequences which is quadratic <code>O(n^2)</code> where n is length of string, but I keep getting time limit exceeded.
  I think there is a more optimised solution that takes advantage of the characters being just <code>&quot;0&quot;</code> and <code>&quot;1&quot;</code> but I cant figure it out (I might be wrong).</p>
  <p>Can anyone help me with a more optimised solution?</p>
  <p>Any input is highly appreciated, thanks.</p>
  <p>Here is the code I tried</p>
  <pre><code>def countSubSequences(s):
      output = 0
      n = len(s)
      dp = [[0]*n]*n
  
      for i in range(n-2,-1,-1):
          for j in range(i+2,n):
              if dp[i+1][j] == dp[i+1][j-1]:
                  dp[i][j] = dp[i][j-1] + 0
              else:
                  dp[i][j] = dp[i][j-1] + (dp[i+1][j] - dp[i+1][j-1])
              
              if s[i] == s[j]:
                  dp[i][j] += j-i-1
  
      for i in range(n):
          for j in range(i+4,n):
              if s[i] == s[j]:
                  output += dp[i+1][j-1]
  
      return output % ((10**9) + 7)
  </code></pre>