Longest Substring With Two Unique Characters

In advance of the interview season coming in the latter half of the summer/early fall, I've begun my interview preparation. :)

Here, I'll tackle the following:

Problem. Given a string $S$, compute the length of the longest substring $S_{ij}$ that contains at most $2$ distinct characters.

Example.

"ab" $\longrightarrow 2$

"aabacde" $\longrightarrow 4$

"aaaaaa" $\longrightarrow 6$

Solution.

I'll present my solution before – after attempting it myself, I discovered another more concise solution. However, I'll present my work below as I think it is much easier to adapt to cases of not just 2 but more unique characters (and also to cases that don't involve Strings and characters but Lists and Objects).

My initial approach was as follows: my intuition was that this problem would admit an easy quadratic solution and a more involved linear time one. I decided to jump straight to the linear time solution!

This would require one (or a constant number of) iteration(s) while keeping track of the optimal solution over the range of iterated values thus far. Since the goal was to maximize the objective, if we had an optimal solution for the range $[i, j]$, no optimal solution for a subrange of $[i, j]$ would be better than the one we had already found. That means we can already cut out unnecessary checks!

So, I distilled my strategy down to the following main ideas:

  1. Need to maintain a "substring" window and slide it across the input string.
  2. Need to keep track of the number of counts per character in the window so that it obeys the two-character constraint.
public static int longestSubstringWithTwoUniqueChars(String S, int n) {

  int l = 0, r = 0;
  Map<Character, Integer> counts = new HashMap<>();
  int maxWindowSize = 0;

  incrementOrCreate(counts, S.charAt(r));

  // Main loop.
  while (r+1 < n) {
    // Grow out the right side until doing so would add a 3rd character.
    while (shouldIncreaseRange(S, r+1, counts)) {
      incrementOrCreate(counts, S.charAt(++r));
    }

    maxWindowSize = Math.max(maxWindowSize, r - l + 1);

    // Shrink out the left side until one of the characters has been completely removed.
    if (r+1 < n) {
      incrementOrCreate(counts, S.charAt(++r));
      while (countsInWindow.keySet().size() == 3) {
        decrementOrRemove(counts, S.charAt(l++));
      }
    }
  }

  return maxWindowSize;
}

The other methods I've included, such as incrementOrCreate are helper methods to make the above code more readable.

/**
 * Whether or not the algorithm should increase its range
 * to include the character at index i.
 *
 * @param S the entire input string
 * @param i the index of the character to consider adding
 * @param counts the character frequencies in the window
 */
private static boolean shouldIncreaseRange(String S, int i, Map<Character, Integer> counts) {
  if (i >= S.length())
    return false;
  if (! counts.containsKey(S.charAt(i)) && counts.keySet().size() == 2)
    return false;
  return true;
}

I have omitted the implementation of the rest of the helper methods as I believe their names are descriptive enough.

The above solution performs in expected $O(n)$ time, as it makes a single traversal through the input string and leverages use of a HashMap and other constant time operations in completion.

In space usage, the size of the HashMap is also constant, as it can only store up to $3$ unique keys throughout iteration. Not bad!

Thanks for reading, and please let me know if there are any errors in my approach.

Joie de vivre!