c# - 是否存在用于从包含给定字符集和计数的输入字符串中查找最小子字符串的 O(n) 算法？

Question

给定一个字符串 s 和一组带计数的字符，找到 s 中包含所有重复其计数次数的字符的最小子字符串。

示例:

charcount = { { 'A', 3 }, { 'B', 1 } }; 
str = "kjhdfsbabasdadaaaaasdkaaajbajerhhayeom" 

---> "aajba" 

我知道如何在 O(n^2) 时间内通过从最小到最大迭代所有子字符串来完成此操作。

可能的函数签名:

string SmallestSubstringWithCharacterCount(Dictionary<char,int> chardic, string source)
{
   // ... 
}

我猜你可以通过某种方式遍历 str 因为一旦你到达

"kjhdfsbabasdadaaaaasdkaaajbajerhhayeom" 
             |
           here

您找到了第一个字符串 "kjhdfsbabasda"，其中包含集合中的所有字符。

Answer 1

是的，线性算法确实存在。

您需要使用初始零计数和 GoodCount 计数器设置额外的 currentcharcount。

制作两个索引指针 - 左和右，并通过输入字符串移动它们。

如果下一个字符来自集合，则在当前字符计数中增加此字符的计数。如果此计数等于目标值，则增加 GoodCount。 向右移动索引，直到 GoodCount 达到字符计数长度 - 现在当前子字符串包含所有需要的字符。

然后向左移动索引，递减计数，并在需要时递减 GoodCount。就在这一步之前，我们有从这里开始的最短子串。

递减 GoodCount 后 - 使用正确的索引重复过程等，以从所有最短的子串中选择最好的。