Code Challenge: Longest Substring Without Repeating Characters - Java Edition

This challenge asks you to find the longest substring without repeating characters in a given string.
Example Inputs and outputs

Input: s = "pwwkew"
Output: 3
The answer is "wke", with the length of 3.

Brute Force

The brute force approach to this kind of problem is pretty straight forward and includes nesting loops. Obviously, this is not an ideal solution, however if you need a quickly produce a solution, this might be it. We can optimize it after it works.

 public int lengthOfLongestSubstring(String s) {
   int n = s.length();

   int res = 0;
   for(int i = 0; i < n; i++){
     for(int j = i; j < n; j++){
       if(check(s, i, j)) {
        res = Math.max(res, j - i + 1);
       } 
      }
     }
    return res;
}

private boolean check(String s, int start, int end) {
  int[] chars = new int[128];

  for(int i = start; i <= end; i++) {
    char c = s.charAt(i);
    chars[c]++;
    if (chars[c] > 1) {
       return false;
    }
   }
  return true;
}

The technique above gives a runtime complexity of O(n^3) and a space complexity of O(min(n,m)). I think we can do better.

Optimized

There is a technique called "sliding window" and it is often used for this kind of problem. It generally works by maintaining a fixed window over the array, and then moving the window forward one element at a time. As the window moves, the algorithm calculates the answer to the problem for the current window. In this case our window isn't "fixed" but we use a similar concept.
We can use a HashSet to store the characters in the "window" [i, j] (where j = i initially). Then we move the index j to the right. If it is not in our HashSet, we bump j to the right. We do this until we find a character already in the HashSet. Now, we found the largest number of substrings without duplicates. Keep this up throughout the whole string i and you will get the answer. This idea can be further optimized by using a map to define a mapping of a character to its index. This allows us to skip characters when we find repeated characters.

Let's see how we might implement it here.

   public int lengthOfLongestSubstring(String s) {
      int ans = 0;
      // map to store character and its index
      Map<Character, Integer> map = new HashMap<>(); 
      for (int end = 0, start = 0; end < s.length(); end++) {
         // if it is in the map, its a duplicate
         if (map.containsKey(s.charAt(end))){
            // move start to new index
            start = Math.max(map.get(s.charAt(end)), start);
         }
         // not in map keep track of how long the window is
         ans = Math.max(ans, end - start + 1);
         // add char to map
         map.put(s.charAt(end), end + 1);
      }
      return ans;
   }

Now this one is much faster with a runtime complexity of O(n) and a space complexity of O(min(m,n)).

Another Optimized

In doing some research for this article, I discovered an even more optimized solution that makes some assumptions about the type of string input. According to this article, "If we know that the charset is rather small, we can mimic what a HashSet/HashMap does with a boolean/integer array as a direct access table. Though the time complexity of query or insertion is still O(1), the constant factor is smaller in an array than in a HashMap/HashSet."

So if we assume the string is ASCI, we can use an integer array with a length of 128.

   public int lengthOfLongestSubstring(String s) {
        Integer[] chars = new Integer[128];

        int left = 0;
        int right = 0;

        int res = 0;
        while (right < s.length()) {
            char r = s.charAt(right);

            Integer index = chars[r];
            if (index != null && index >= left && index < right) {
                left = index + 1;
            }

            res = Math.max(res, right - left + 1);

            chars[r] = right;
            right++;
        }

        return res;
    }

We see from this problem that the brute force technique to solve a problem can be very slow, however, it can help us reason about the problem. The sliding window technique was also introduced to reduce loops needed in these types of problems. Remember you can reach for the Sliding Window if you hear the following things in the problem: Array, String, Sub Array, Sub String, Largest Sum, Maximum Sum, Minimum Sum. We also see that data structures can help us optimize our code even more. Let me know in the comments if you have other examples of sliding windows.

Extra

I've been learning Scala code and I was looking into various Scala solutions. I found one on Leet Code that I thought was pretty cool by Imran Sarwar. His solution uses a function called scanLeft. Using scan left, also called prefix scan, you can calculate cumulative values over a sequence. Basically, it applies a binary operation to the current value and the next value. The scan left operation results in a new sequence of values, where each value is the cumulative result of the binary operation applied to the first n values. The key in his solution is the binary operator where it does the "windowing" until it finds a previously calculated character.

def lengthOfLongestSubstring(s: String): Int = {
    s.scanLeft("")((currStr: String, currChar: Char) => 
    currStr.substring(1 + currStr.indexOf(currChar)) + currChar)
    // Up to this point we would get vector like this
    // Vector(, a, ab, abc, bca, cab, abc, cb, b)
    // now if we take max of length would get the answer
    .map(_.length)
    .reduce(Math.max)
}

Photo by Sean Patrick: https://www.pexels.com/photo/brown-wood-dock-1057663/