需要删除的最小字符数

Question

原始问题:

如果单词中的每两个字母,如果第一个出现x次数而第二个出现y次数,则单词为K-good ,则|x - y| ? K.

给出一些单词w,他需要移除多少个字母才能使它成为K-good？
问题链接.

我已经解决了上述问题,我没有要求解决上述问题

我只是第一次误读了这个陈述,只是想到我们怎么能在线性时间线上解决这个问题,这只会引起一个新的问题

修改问题

如果单词中的每两个连续字母,如果第一个出现x次数而第二个出现y次数,则单词为K-good|x - y| ? K.

给出一些单词w,他需要移除多少个字母才能使它成为K-good？

这个问题是否可以在线性时间内解决,我考虑过但却找不到任何有效的解决方案.

解决方案

我的方法:我不能接近我的迷恋,但她是我解决这个问题的方法,尝试一切(来自电影Zooptopia)

即

for i range(0,1<<n):   // n length of string
    for j in range(0,n):
          if(i&(1<<j) is not zero): delete the character
   Now check if String is K good 

适用N于范围 10^5.时间复杂性:该维度中不存在时间.

有没有任何线性解决方案,像stackoverflow的人一样简单和甜蜜.

For Ex:
String S = AABCBBCB and K=1


   If we delete 'B' at index 5 so String S = AABCBCB which is good string
    F[A]-F[A]=0
    F[B]-F[A]=1
    F[C]-F[B]=1
    and so on

我想这是一个简单的例子我可以将更复杂的例子删除为I元素makens(I-1)和(I + 1)连续

Answer 1

这个问题有线性解吗？

考虑一下这个词DDDAAABBDC。这个词是 3-good，因为D和C是连续的并且，并且通过使和不连续card(D)-card(C)=3删除最后一个D使其成为 1-good 。DC

相反，如果我认为DABABABBDC哪个是 2-good，则删除最后一个DmakeC和BContinuous，并将该单词的 K 值增加到 3。

这意味着在修改后的问题中，单词的 K 值由每个字母的基数和每对连续字母的基数决定。

通过删除一个字母，我减少了该字母的基数以及它所属的对的基数，但我也增加了其他对的基数（可能会创建新的）。

同样重要的是要注意，如果在原始问题中，所有字母都是等效的（我可以无差别地删除任何字母），而在修改后的问题中不再是这种情况。

作为结论，我认为我们可以安全地假设“连续字母”约束使得任何字母/单词的问题都无法在线性时间内解决。