> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/two-pointers/window/longest-substring-without-repeating-characters.md).

# Longest Substring Without Repeating Characters

## Question ([LC.3](https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description))

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

## Example

```
I: "abcabcbb"
O: 3 because "abc"
I: "bbbbb"
O: 1 because "b"
I: "pwwkew"
O: 3 because "kew"
```

## Analysis

The brute force approach is to try all substrings.

## Brute Force

```java
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    Set<Character> noRepeat = new HashSet<>();
    int maxLength = Integer.MIN_VALUE;

    for (int i = 0; i < s.length(); i++) {
        noRepeat.clear();
        for (int j = i; j < s.length(); j++) {
            if (noRepeat.contains(s.charAt(j))) {
                break;
            }
            noRepeat.add(s.charAt(j));
        }
        maxLength = Math.max(maxLength, noRepeat.size());
    }
    return maxLength;
}
```

## Optimization

Again, `j` doesn't have to go back to `i` after find each non-repeating substring. We can shrink then extend the current non-repeating substring.

```
S   p  w  w  k  e  w
L1  i->j
L2     i(j)
L3        i->j
L4        i---->j
L5           i----->j
L6               i->j
```

## Optimized Code

```java
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    Set<Character> noRepeat = new HashSet<>();
    int maxLength = Integer.MIN_VALUE;
    int j = 0;
    for (int i = 0; i < s.length(); i++) {
        // extend
        while (j < s.length() && noRepeat.add(s.charAt(j))) {
            j++;
        }
        maxLength = Math.max(maxLength, noRepeat.size());
        // shrink
        noRepeat.remove(s.charAt(i));
    }
    return maxLength;
}
```