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.

\[\fbox{abcde} \mbox{fd} \implies \fbox{abcdef} \mbox{d} \implies \mbox{abcd} \fbox{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

\[\mbox{ab} \fbox{bcd} \mbox{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

\[\fbox{abbcda}\]

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