string - 查找字符串对

Question

我试图练习一些基于字符串和算法的问题，我偶然发现了一个具有以下措辞的问题:

你有一个长度为 N 的字符串 x，它由小写的英文字母组成。你必须找到 x 中的子字符串 S 的数量，使得 0 <= d < c < b < a <= N - 1和 x[a] == x[c] and x[b] == x[d] .

例如: x = "ababa"答案是s=2因为有两个字符串满足上述条件: abab和 baba .

解决这个问题的最佳方法是什么？

提前致谢。

Answer 1

提示:如果 f(a) 返回 a 右边的 ab 组合的数量，那么:

f(next-a-to-the-left) = 
  f(a) + count of b's to the right
         of next-a-to-the-left

对于每个b，有

f(next-a-to-the-right) * count of a's to the left

有效组合。