在包含相等数量的a，b，c的字符串中找到子字符串的数量

Question

我正在努力解决这个问题。现在，我能够获得递归解决方案：

如果DP[n]给出以字符串的第n个字符结尾的漂亮的子字符串（在问题中定义）的数量，则要查找DP[n+1]，我们从第（n + 1）个字符向后扫描输入字符串，直到找到第i个字符，使得子字符串从第i个字符开始到第（n + 1）个字符结束都是很漂亮的。如果找不到这样的人，DP[n+1] = 0。

如果这样的字符串被找到，那么，DP[n+1] = 1 + DP[i-1]。

麻烦的是，这种解决方案使一个测试用例超时。我怀疑是向后扫描部分存在问题。我的解决方案的总体时间复杂度似乎为O(N^2)。输入数据的大小似乎表明问题需要O(NlogN)解决。

Answer 1

您实际上并不需要动态编程。您可以通过遍历字符串一次，然后在每个字符之后，将状态（到目前为止遇到的a，b和c的相对数量）存储在字典中来实现。该词典的最大大小为N + 1，因此总时间复杂度为O（N）。

如果发现字符串的某个点上的a比b多5个，而c则比b多7个，并且在字符串的另一点处发现相同的情况，那么您知道这两个点之间的子字符串包含相等数量的a，b和c。

让我们来看一个使用输入“ dabdacbdcd”的示例：

       a,b,c

   ->  0,0,0  
d  ->  0,0,0  
a  ->  1,0,0  
b  ->  1,1,0  
d  ->  1,1,0  
a  ->  2,1,0  
c  ->  2,1,1  ->  1,0,0  
b  ->  1,1,0  
d  ->  1,1,0  
c  ->  1,1,1  ->  0,0,0    
d  ->  0,0,0  

因为我们只对a，b'a和c的数目之间的差异感兴趣，而不是对实际数目感兴趣，所以我们通过从所有三个数字中减去最低的数目来减少状态2,1,1为to 1,0,0。

我们以这些状态及其发生次数的字典作为结尾：

0,0,0  ->  4  
1,0,0  ->  2  
1,1,0  ->  4  
2,1,0  ->  1  

仅出现一次的状态并不表示abc相等的子字符串，因此我们可以将其丢弃；然后，我们剩下这些状态的重复：

4, 2, 4  

如果状态发生两次，则在这两个位置之间有1个abc相等的子字符串。如果一个状态发生4次，则它们之间有6个abc-equal子字符串；例如，状态1,1,0出现在以下几点：

dab|d|acb|d|cd  

这4点中的2点之间的每个子串都等于abc等于：

d, dacb, dacbd, acb, acbd, d  

通常，如果一个状态出现n次，则表示1 + 2 + 3 + ... + n-1个abc相等子字符串（或更容易计算：n-1×n / 2）。如果我们对字典中的每个计数进行计算，则总和就是我们的解决方案：

4  ->  3 x 2 = 6  
2  ->  1 x 1 = 1  
4  ->  3 x 2 = 6  
              --
              13  

让我们通过查找这13个子字符串来检查结果：

 1  d---------  
 2  dabdacbdc-  
 3  dabdacbdcd  
 4  -abdacbdc-  
 5  -abdacbdcd  
 6  --bdac----  
 7  ---d------  
 8  ---dacb---  
 9  ---dacbd--  
10  ----acb---  
11  ----acbd--  
12  -------d--  
13  ---------d