leetcode_rust/
length_of_longest_substring.rs

1#![allow(dead_code)]
2
3// slide window from left to right
4pub fn length_of_longest_substring(s: String) -> i32 {
5    use std::collections::HashSet;
6
7    let mut set = HashSet::new();
8    let mut longest = 0;
9    let mut i = 0;
10    let mut j = 0;
11    let s = s.into_bytes();
12    while i < s.len() && j < s.len() {
13        if !set.contains(&s[j]) {
14            set.insert(s[j]);
15            j += 1;
16            longest = usize::max(longest, j - i);
17        } else {
18            set.remove(&s[i]);
19            i += 1;
20        }
21    }
22
23    longest as i32
24}
25
26// opt: move the window more than one step by look up hash map
27pub fn length_of_longest_substring2(s: String) -> i32 {
28    use std::collections::HashMap;
29
30    let mut map = HashMap::new();
31    let mut longest = 0;
32    let mut i = 0;
33    let mut j = 0;
34    let s = s.into_bytes();
35    while j < s.len() {
36        if map.contains_key(&s[j]) {
37            i = usize::max(map[&s[j]], i);
38        }
39        longest = longest.max(j + 1 - i);
40        map.insert(s[j], j + 1);
41        j += 1;
42    }
43
44    longest as i32
45}
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test1() {
53        assert_eq!(length_of_longest_substring(String::from("pwwkew")), 3);
54    }
55
56    #[test]
57    fn test2() {
58        assert_eq!(length_of_longest_substring2(String::from("pwwkew")), 3);
59    }
60}
leetcode_rust/length_of_longest_substring.rs

leetcode_rust/
length_of_longest_substring.rs
