Charging Station: The Frequency Array
Learn how we can make the FREQUENTWORDS algorithm work faster, transform patterns, and different algorithms for frequent words problem.
To make FrequentWords faster, we’ll think about why this algorithm is slow in the first place. It slides a window of length k down Text, identifying a k-mer Pattern of Text at each step. For each such k-mer, it must slide a window down the entire length of Text in order to compute PatternCount(Text, Pattern). Instead of doing all this sliding, we aspire to slide a window down Text only once. As we slide this window, we’ll keep track of the number of times that each k-mer Pattern has already appeared in Text, updating these numbers as we proceed.
Ordering 4 k-mers
To achieve this goal, we’ll first order all 4 ...