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

Input | Output | Longest substring |
---|---|---|

`"abcdabcbd"` |
4 | `"abcd"` |

`"aaaaaa"` |
1 | `"a"` |

`"tidddosa"` |
4 | `"dosa"` |

`"au"` |
2 | `"au"` |

## Solution

We can solve this in O(n) using a sliding window. The `l`

and `r`

are the left and right indices of the window, respectively. We start with `l`

and `r`

at 0, representing a window one item wide and then move `r`

to the right item by item. We check the set to see if we’ve seen the item before and if so we get the size of the window (`r - l`

) and update `longest`

if applicable. When we find an item we’ve already seen we remove the character at position `l`

and move it the right, continuing until we remove the item at `r`

from the set. We then start again.

```
use std::collections::HashSet;
use std::cmp::max;
fn length_of_longest_substring(s: String) -> i32 {
let chars: Vec<char> = s.chars().collect();
if chars.len() < 2 { return chars.len() as i32}
let mut l: usize = 0;
let mut r: usize = 0;
let mut longest: usize = 0;
// We're dealing with the lowercase English alphabet so we can allocate
// our set to the max size we'll ever need.
let mut seen: HashSet<char> = HashSet::with_capacity(26);
while r < chars.len() {
if seen.contains(&chars[r]) {
seen.remove(&chars[l]);
l += 1;
}
else {
longest = max(longest, r - l);
seen.insert(chars[r]);
r += 1;
}
}
(longest + 1) as i32
}
#[test]
fn length_of_longest_substring_test() {
assert_eq!(length_of_longest_substring("".to_string()), 0);
assert_eq!(length_of_longest_substring("abcdabcbd".to_string()), 4);
assert_eq!(length_of_longest_substring("aaaaaa".to_string()), 1);
assert_eq!(length_of_longest_substring("tidddosa".to_string()), 4);
assert_eq!(length_of_longest_substring("au".to_string()), 2);
}
```

## LeetCode says…

```
Runtime: 4 ms, faster than 76.05% of Rust online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 2.1 MB, less than 100.00% of Rust online submissions for Longest Substring Without Repeating Characters.
```

Not the fastest implementation, but I think it’s easy to understand. I’d be interested to see what others have done to make it faster, so ping me on social media if you’ve got a faster solution.

Thanks for reading! Please feel free to send me an email to talk more about this (or anything else for that matter).