长度为 5 的回文子序列的数量

Question

给定一个字符串s，return长度为5的回文子序列的数量。

测试用例 1：

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

测试用例 2：

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

字符串的最大长度：700

我的 TLE 方法：O(2^n)

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

非常感谢任何意见...

Answer 1

每当2个字符匹配时，我们只需要找出这2个字符之间可能有多少个长度为3的回文。

例如：

a bcbc a
^      ^
|_ _ _ |

在上面的例子中，你可以找到2个长度为3的回文，即bcb和cbc。因此，我们可以将长度为5的回文序列制成abcba或acbca。因此，答案是 2.

如果我们在第一次执行时不缓存结果，计算每个子字符串可能有多少个长度为 3 的回文可能会很耗时。因此，缓存这些结果并将它们重新用于由其他 2 个字符匹配生成的查询。 (a.k.a dynamic programming)
这样，解就变成二次 O(n^2) 时间，其中 n 是字符串的长度。

片段：

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

更新：

 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]);

上面这行基本就是这个意思,

对于任意子串，比如bcbcb，匹配first和last b，总共3个回文长度可以相加
- bcbc 的可能总数。
- cbcb 的可能总数。
- bcbcb 的可能总数（在 if 条件下为 (j - i - 1)）。
dp[i][j] 对于手头的当前子字符串。
dp[i][j-1] - 添加前面的长度为 3 的子串计数。在本例中，bcbc.
dp[i + 1][j]，添加以当前索引结尾的子字符串，不包括第一个字符。（这里，cbcb）。
dp[i + 1][j] == dp[i + 1][j-1] ? 0 : dp[i + 1][j] - dp[i + 1][j - 1] 这基本上是为了避免对内部子字符串进行重复计数，并且仅在计数存在差异时才添加它们。

长度为 5 的回文子序列的数量

Number of palindromic subsequences of length 5

string

algorithm