Number of palindromic subsequences of length 5

Question

Given a String s, return the number of palindromic subsequences of length 5.

Test case 1:

input : "abcdba"
Output : 2
"abcba" and "abdba"

Test case 2:

input : "aabccba"
Output : 4
"abcba" , "abcba" , "abcba" , "abcba"

Max length of String: 700

My TLE Approach: O(2^n)

https://www.online-java.com/5YegWkAVad

Any inputs are highly appreciated...

Answer 1

• Whenever 2 characters match, we only have to find how many palindromes of length 3 are possible in between these 2 characters.

For example:

a bcbc a
^      ^
|_ _ _ |

In the above example, you can find 2 palindromes of length 3 which is bcb and cbc. Hence, we can make palindromic sequence of length 5 as abcba or acbca. Hence, the answer is 2.

• Computing how many palindromes of length 3 are possible for every substring can be time consuming if we don't cache the results when we do it the first time. So, cache those results and reuse them for queries generated by other 2 character matches. (a.k.a dynamic programming)

• This way, the solution becomes quadratic O(n^2) time where n is length of the string.

Snippet:

private static long solve(String s){
  long ans = 0;
  int len = s.length();
  long[][] dp = new long[len][len];
  
  /* compute how many palindromes of length 3 are possible for every 2 characters match */
  for(int i = len - 2;i >= 0; --i){
    for(int j = i + 2; j < len; ++j){
      dp[i][j] = dp[i][j-1] + (dp[i + 1][j] == dp[i + 1][j-1] ? 0 : dp[i + 1][j] - dp[i + 1][j - 1]);
      if(s.charAt(i) == s.charAt(j)){
        dp[i][j] += j - i - 1;
      }
    }
  }
  
  /* re-use the above data to calculate for palindromes of length 5*/ 
  for(int i = 0; i < len; ++i){
    for(int j = i + 4; j < len; ++j){
      if(s.charAt(i) == s.charAt(j)){
        ans += dp[i + 1][j - 1];
      }
    }
  }
  
  //for(int i=0;i<len;++i) System.out.println(Arrays.toString(dp[i]));
  
  return ans;
} 

Online Demo

Update:

 dp[i][j] = dp[i][j-1] + (dp[i + 1][j] == dp[i + 1][j-1] ? 0 : dp[i + 1][j] - dp[i + 1][j - 1]);

The above line basically mean this,

• For any substring, say bcbcb, with matching first and last b, the total 3 length palindromes can be addition of
  • The total count possible for bcbc.
  • The total count possible for cbcb.
  • The total count possible for bcbcb (which is (j - i - 1) in the if condition).
• dp[i][j] For the current substring at hand.
• dp[i][j-1] - Adding the previous substring counts of length 3. In this example, bcbc.
• dp[i + 1][j], Adding the substring ending at current index excluding the first character. (Here, cbcb).
• dp[i + 1][j] == dp[i + 1][j-1] ? 0 : dp[i + 1][j] - dp[i + 1][j - 1] This is to basically avoid duplicate counting for internal substrings and only adding them if there is a difference in the counts.