string - 最多 n 个位置不同的字符串数？

Question

我得到了一个仅由 's','t','u','v' 作为字符组成的字符串 T。我想找到长度为 |T| 的字符串数它最多与 T 不同 n 个位置。而且每个这样的字符串在三个不同的位置不能有相同的字符，这些位置由相同的距离分隔。我的方法是使用动态编程方法，使得 dp[i][j][k] 表示长度为 i 的此类字符串的数量，在 j 位置不同而在第 k 个字符结束，其中 k=s,t,u,v 。

if(k在T的第i个字符相同)

dp[i][j][k]=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][ 2]-(由于在第i个位置添加了k并且违反了相同分隔距离的条件而额外的字符串)

但我知道这是错误的？

例如，假设 T ='sstt' 并且我们必须找到最多 2 个位置不同的字符串，然后在三个不同位置以相同距离分隔的不具有相同字符的字符串是 'tstt'、'ssts' 和等等

Answer 1

这看起来真的很有趣。或许您可以枚举两对的数量，然后继续计算？