5
$\begingroup$

Given a string $S$ of length $n$, and a number $k$, count the number of substrings (regardless of their length) that contain exactly $k$ different characters.

The obvious solution takes $O(n^2)$ time (fix substring start point, and move its end point while keeping track of the set of seen characters).

Is there a way to do that in $O(n)$ time? Or at least in $O(n c)$ time, where $c$ is the number of unique characters in the string $S$?

I tried to keep track of two pointers (start and end) and move only one of them forward at each step, while updating the hash table with character counts. But counting substrings became really messy.

$\endgroup$
  • 1
    $\begingroup$ It seems your question is not clear. Do all the substrings you want to find have length $k$, or can they have arbitrary length (as long as they use only $k$ different symbols)? $\endgroup$ – Raphael Jan 3 '17 at 7:27
  • $\begingroup$ Arbitrary length, just as long as there are exactly $k$ different symbols. $\endgroup$ – max Jan 3 '17 at 16:23
5
$\begingroup$

You can solve this in $O(n)$ time using two (well, three) pointers that both move leftward.

Let $S$ be the string. We'll let $i$ range from $n$ down to $1$, and for each value of $i$, we're going to count the number of substrings that start at position $i$.

For each $i$, find the smallest $j_\text{min} \ge i$ such that $S[i..j_\text{min}]$ has exactly $k$ unique characters as well as the largest $j_\text{max} \ge i$ such that $S[i..j_\text{max}]$ has exactly $k$ unique characters. You can do this efficiently, by keeping an array (or hashtable) with character counts for $S[i..j_\text{min}]$ and one with character counts for $S[i..j_\text{max}]$; you'll update these each time you decrement $i$, $j_\text{min}$, or $j_\text{max}$. (In addition to the array/hashtable, also keep track of the number of of characters with non-zero count, and update this each time you update the array or hashtable.) When you decrement $i$, you can update the array/hashtable with character counts for $S[i..j_\text{min}]$, then use that to see whether you need to decrease $j_\text{min}$ and by how much (updating the array/hashtable each time you decrement $j_\text{min}$). Same for $j_\text{max}$.

Finally, sum up the counts you get for each value of $i$.

Note that $j_\text{min}$ starts out at $n$ and only ever decreases: when you decrement $i$, $j_\text{min}$ can only ever get smaller (but not bigger). So, you'll only need to decrement $j_\text{min}$ (and update the array/hashtable) at most $n$ times: it starts out at $n$, and only ever decreases, and never gets smaller than $1$, so it can only be decreased at most $n$ times. The same is true for $j_\text{max}$. Consequently, we do at most $O(n)$ updates to the array/hashtable (summed up over all the steps of the algorithm), so the total running time of this algorithm is $O(n)$.

Credit: Thanks to @aaaaajack for a major improvement to my algorithm, and to @Raphael for further improvements.

$\endgroup$
  • $\begingroup$ I assume you mean $j_{min/max} \ge i$ rather than $j_{min/max} \ge n/2$. The problem is that when you decrement $i$, $j_{min/max}$ could potentially decrease by as much $O(n)$. Even though you maintain the hash table, the naive way to find the new value of $j_{min/max}$ requires decreasing them by 1, then by 2, etc. until you get it right. This is $O(n^2)$. You might be able to do a binary search, but that requires maintaining hash table at each location, which probably results in $O(n c \log n )$. I'll try that, but was really hoping for $O(n)$. $\endgroup$ – max Jan 3 '17 at 6:43
  • $\begingroup$ @max, yes, $\ge i$, good catch. Edited. Thanks. I think the running time is still only $O(n)$. $j_\text{min}$ decreases monotonically throughout the lifetime of the algorithm, so even though you might have to decrease it several times in one step, the total amount you can decrease $j_\text{min}$ is at most $n$: it starts out at $n-1$, and decreases to $0$ or larger, so the total amount of decrease is $O(n)$. When we decrement $i$, $j_\text{min}$ can only decrease (never increase). So, monotonicity saves us. $\endgroup$ – D.W. Jan 3 '17 at 6:47
  • 1
    $\begingroup$ "You should be able to do this efficiently, by keeping a hash table with character counts" -- if you represent symbols by numbers $0..m$ then you can just count in an array. Also, you'll of course maintain the current number of different characters in the interval under consideration, not recompute it every time from the array. This will indeed lead to a very efficient algorithm then. $\endgroup$ – Raphael Jan 3 '17 at 19:44
  • $\begingroup$ @Raphael: That's what I thought. But now take strings with Unicode code points (there are over a million) and then strings with Unicode grapheme clusters (basically unlimited), and you need a hash table. $\endgroup$ – gnasher729 Jan 4 '17 at 21:18
  • $\begingroup$ @gnasher729 I usually consider such technicalities beyond the scope of this site. But sure, if you have billions of potential symbols but only ever see a few dozens, you need more compact set representations. $\endgroup$ – Raphael Jan 4 '17 at 21:45
2
$\begingroup$

As is often the case with substring problems, suffix trees provide an answer.

  1. Construct the suffix tree of your string.
  2. In one traversal, annotate every node with the set of characters on the path from it to the root.
  3. Check all nodes and output those whose associated set has $k$ members.

All steps take time in $O(n)$ (under the usual assumptions).

You can make this faster by aborting a branch in step 2 if the set reaches size $k+1$ (they never shrink) and checking/returning nodes when you visit them. Also, you don't need to actually store the sets; carrying one representation you can efficiently update (e.g. bit vectors) around is quite enough.

Disclaimer: in order to achieve the running-time bounds it may be necessary to maintain character sets of compound edges during step 1.

$\endgroup$
  • 2
    $\begingroup$ Damn, it really seems like the answer to every problem I can't solve is "suffix tree". I guess I'll read up on them. $\endgroup$ – max Jan 3 '17 at 6:45
  • 1
    $\begingroup$ Suffix tree is strong but I'm not a fan of overkilling every problem with suffix data structures... D.W.'s solution does work in $O(n)$ and the two-pointer approach is quite common. $\endgroup$ – aaaaajack Jan 3 '17 at 7:14
  • 1
    $\begingroup$ @max Hehe... they are a beautiful thing for sure. It never stops to amaze me that they have size $O(n)$ and can be built in that time, too. Thanks, Ukkonen! $\endgroup$ – Raphael Jan 3 '17 at 7:23
  • $\begingroup$ Let's continue the philosophical discussion in chat. $\endgroup$ – Raphael Jan 3 '17 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.