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).