string - 给定每个字符计数的字符串的子字符串数

Question

给定一个字符串 (s) 和一个整数 k，我们需要找到所有不同字符恰好出现 k 次的子字符串的数量。
示例:s = "aabbcc", k = 2
输出:6
子串 [aa, bb, cc, aabb, bbcc and aabbcc] 包含频率为 2 的不同字符。
我能想到的方法是遍历所有子串并存储当前子串的频率，并在频率等于k时增加结果。这将导致 O(n*n) 的最坏情况复杂度，其中 n 是字符串 s 的长度。
有没有更好的方法来解决这个问题？

Answer 1

我们可以在 O(n * log(size_of_alphabet)) 中解决这个问题。让 f(i) 表示以第 i th 个字符结尾的最有效的子字符串。然后:

f(i) ->
  1 + f(j - 1)
  
where j is the rightmost index smaller
than or equal to i where s[j..i] is a
valid substring and (j - 1) is inside
the current window. Call s[j..i] the
"minimal" valid substring ending at
index i.

我们的窗口的一个不变式是，如果一个字符被看到 k + 1 次，我们将左边界移动到窗口中该字符最左边的实例。这保证了当前窗口中串联的有效子串中的任何两个子串不能有共享字符，因此保持有效串联。
每次我们到达 k 字符 c 的第 i 实例时，最右边的索引小于或等于 s[j..i] ，其中 k 是有效子字符串，必须从窗口中计数小于 k 的所有字符的右侧开始。为了找到最右边的这样的索引，我们可能还需要在窗口中已经看到的有效相邻子串之前移动。
为了找到那个索引，我们可以维护一个 max indexed-heap ，它存储我们窗口中每个不同字符的最右边的实例，当前计数小于 j ，按它们的索引优先，这样我们的 O(log(size_of_alphabet)) 总是在堆的根(或堆是空的)。堆被索引，这允许我们删除 O(1) 中的特定元素。
我们还保留了窗口中已经看到的有效最小子串的左右边界索引。我们可以为 O(1) 更新使用双端队列，因为有效的子字符串可以出现在另一个或包含现有子字符串的右侧。我们为 k 查找保留了左边界的哈希图。
此外，我们必须保留窗口中每个不同字符的计数，以保持我们的不变性，在 ojit_code 之上没有这样的计数，以及它们在窗口中最左边的索引，用于有效的子字符串前提条件。
程序:

for each index i in s:
  let c be the character s[i]
  
  if s[i] is the (k+1)th instance of c in the window:
    move the left bound of the window
    just past the leftmost instance of
    c in the window, removing all
    elements in the heap who's rightmost
    instance we passed while updating
    our window; and adding to the heap
    the rightmost instance of characters
    who's count has fallen below k
    as we move the left bound of
    the window. If the boundary moves
    past the left bound of valid minimal
    substrings, remove their boundaries
    from the queue, and their left bound
    from the hashmap.
    
  if s[i] is the kth instance of c:
    remove the previous instance of c
    from the heap.
    if the leftmost instance of c in the
    window is to the right of the heap
    root:
      if (root_index + 1) is the
      left bound of a valid minimal
      substring in our queue:
        we must be adding to the right
        of all of them, so add a new
        valid minimal substring, starting
        at the next index after the
        rightmost of those that ends
        at i
      otherwise:
        add a new valid minimal substring,
        starting at (root_index + 1)
        and ending at i
    
  otherwise:
    remove the previous instance of c
    in the heap and insert this one.
  

例如:

01234567
acbbaacc  k = 2

0 a  heap: (0 a)

1 c  heap: (1 c) <- (0 a)

2 b  heap: (2 b) <- (1 c) <- (0 a)

3 b  kth instance, remove (2 b)
     heap: (1 c) <- (0 a)
     leftmost instance of b is to the
     right of the heap root.
     check root + 1 = 2, which points
     to a new valid substring, add the
     substring to the queue
     queue: (2, 3)
     result: 1 + 0 = 1
     
4 a  kth instance, remove (0 a)
     heap: (1 c)
     queue: (2, 3)
     result: 1
     leftmost instance of a is left
     of the heap root so continue
     
5 a  (k+1)th instance, move left border
     of the window to index 1
     heap: (1 c)
     queue: (2, 3)
     result: 1
     
     (5 a) is now the kth instance of
     a and its leftmost instance is to
     the right of the heap root.
     check root + 1 = 2, which points
     to a valid substring in the queue,
     add new substring to queue
     heap: (1 c)
     queue: (2, 3) -> (4, 5)
     result: 1 + 1 + 1 = 3
     
6 c  kth instance, remove (1 c)
     heap: empty
     add new substring to queue
     queue: (1) -> (2, 3) -> (4, 5) -> (6)
     (for simplicity, the queue here
     is not labeled; labels may be needed
     for the split intervals)
     result: 3 + 1 + 0 = 4
     
7 c  (k+1)th instance, move left border
     of the window to index 2, update queue
     heap: empty
     queue: (2, 3) -> (4, 5)
     result: 4
     
     (7 c) is now the kth instance of c
     heap: empty
     add new substring to queue
     queue: (2, 3) -> (4, 5) -> (6, 7)
     result: 4 + 1 + 2 = 7