Algorithm visualization

We've kicked off a series of algorithm coding katas at work. As something of an algorithms and data viz geek I thought I'd take part. One of the first problems is Broken Keyboard from Sphere Online Judge. The main challenge for me was just understanding what the problem was trying to describe. Once that clicked it's pretty straightforward to propose some sort of sliding window approach which makes use of the fact we don't need to repeat work.

With an algorithm in mind we can turn to visualizing it. I've been learning d3 as part of my pub map project. My sources of inspiration are often the examples by the creator of d3, Mike Bostock. He has an excellent page on visualizing algorithms which I use as the basis of this work.

So what's going on? We maintain two pointers, i and j. The first points to the start of the substring, and the other to the end of the substring (technically one past the end). These are initialized to 0 and 1. The algorithm works by increasing j if possible. We can extend the substring if adding the next character does not take us over our limit of uniqie characters. Only if we cannot extend the substring, we make the substring shorter by increasing i by one. The algorithm is greedy in the sense it return the first longest substring present. The algorithm terminates when j reaches the end of the string.

For me the most interesting part is how to efficiently determine if it is possible to add the next character to the substring. I opted for maintaining a histogram of character frequency. For ease of implementation I simply use a Javascript array. It might be interesting to explore better approaches.

Here’s the code:

longestSubstring(a, m) {
    var i = 0;
    var j = 1;

    var longestSubtring = [i, j];

    var hist = Array(128).fill(0);
    hist[a[i]]++;

    while (j < a.length) {
        hist[a[j]]++;

        if (hist.map(function(x) { return x > 0; }).reduce(function(a, b) { return a + b; }) <= m) {
            j++;
        } else {
            hist[a[j]]--;
            if (hist[a[i]] > 0) hist[a[i]]--;
            i++;
        }

        if ((j - i) > (longestSubtring[1] - longestSubtring[0])) {
            longestSubtring = [i, j];
        }
    }

    return longestString;
}