Longest Substring Without Repeating Characters

Table of contents

1. Problem
2. Solution

---

Problem

Given a string s, find the length of the longest substring without repeating characters.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

---

Solution

The main idea is to use an imaginary sliding window.

Until we see a repeated character, we just can keep expanding the window.

However, once we see a repeated character, the starting point of the window needs to be moved to the right until the last occurrence of the repeated character is no longer in the window.

$$\boxed{\text{abcde}}\text{fd}⟹\boxed{\text{abcdef}}\text{d}⟹\text{abcd}\boxed{\text{efd}}$$

So, we should to keep track of the last occurrence of each character.

I will be using a HashMap<Character, Integer> to do this, where each character is mapped to its index of last occurrence.

HashMap<Character, Integer> seen = new HashMap<>();

int maxLen = 0;  // Max found so far
int curLen = 0;  // Size of current window

for (int j = 0; j < s.length(); j++) {
  Character c = s.charAt(j);
  if (seen.containsKey(c)) { // Found a repeated character
    int i = seen.get(c);  // Retrieve index of last occurrence
    if (j - curLen > i) {  // If last occurrence is not within window
      curLen++;
    } else {
      curLen = j - (i + 1) + 1;  // Calculate new window size
    }
    seen.replace(c, j);  // Update last occurrence
  } else {
    curLen++;  // Expand window
    seen.put(c, j);  // Record last occurrence
  }
  maxLen = Math.max(maxLen, curLen);
}

return maxLen;

Everything is straightforward except for:

if (j - curLen > i) {  // If last occurrence is not within window
  curLen++;
} else {
  curLen = j - (i + 1) + 1;  // Calculate new window size
}

What is the if statement doing?

Take the example of abbcda. When we see the last a at index 5, the window looks like

$$\text{ab}\boxed{\text{bcd}}\text{a}$$

The window should now ignore everything before the second b, but the HashMap still has a -> 0 in it.

Calculating j - (i + 1) + 1 will give us the wrong window of

$$\boxed{\text{abbcda}}$$

so we have to make the window ignore everything outside of current window.