leetcode/
longest_substring_without_repeating_characters.rs

1//! # 3. 无重复字符的最长子串
2//!
3//! 给定一个字符串 `s`，请你找出其中不含有重复字符的**最长子串**的长度。
4//!  
5//! ## 示例 1:
6//!
7//! ```text
8//! 输入: s = "abcabcbb"
9//! 输出: 3
10//! 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
11//! ```
12//!
13//! ## 示例 2:
14//!
15//! ```text
16//! 输入: s = "bbbbb"
17//! 输出: 1
18//! 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
19//! ```
20//!
21//! ## 示例 3:
22//!
23//! ```text
24//! 输入: s = "pwwkew"
25//! 输出: 3
26//! 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
27//!      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
28//! ```
29//!  
30//!
31//! 提示：
32//!
33//! * `0 <= s.length <= 5 * 104`
34//! * `s` 由英文字母、数字、符号和空格组成
35//!
36pub struct Solution;
37
38impl Solution {
39    pub fn length_of_longest_substring(s: String) -> i32 {
40        Self::impl_sliding_window(&s)
41    }
42
43    fn impl_sliding_window(s: &str) -> i32 {
44        let last_index = std::collections::HashMap::new();
45        let start = 0;
46        let max_length = 0;
47        let init = (max_length, start, last_index);
48        s.char_indices()
49            .fold(init, |(max_length, last_start, mut last_index), (idx, c)| {
50                let new_start = last_index.insert(c, idx).map_or(last_start, |pos| last_start.max(pos + 1));
51                (max_length.max(idx - new_start + 1), new_start, last_index)
52            })
53            .0 as i32
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    #[test]
60    fn test() {
61        use super::Solution;
62        assert_eq!(3, Solution::length_of_longest_substring("abcabcbb".to_string()));
63        assert_eq!(1, Solution::length_of_longest_substring("bbbbb".to_string()));
64        assert_eq!(3, Solution::length_of_longest_substring("pwwkew".to_string()));
65        assert_eq!(1, Solution::length_of_longest_substring(" ".to_string()));
66        assert_eq!(6, Solution::length_of_longest_substring("bbtablud".to_string()));
67        assert_eq!(3, Solution::length_of_longest_substring("aabaab!bb".to_string()));
68    }
69}
leetcode/longest_substring_without_repeating_characters.rs

leetcode/
longest_substring_without_repeating_characters.rs
