Skip to main content

Longest Substring Without Repeating Characters

算是个 DP 题?所求字符串的特点是每个字符在原串中距上个相同字符的距离数值大于在结果串中的位置,所以一遍扫描记录上次出现位置与当前长度做比较即可 On & On

impl Solution {    pub fn length_of_longest_substring(s: String) -> i32 {        use std::collections::HashMap;        use std::convert::TryInto;        let mut map: HashMap<u8, i32> = HashMap::new();        let mut res = 0;        let mut cur = 0;        for (i, c) in s.as_bytes().iter().enumerate() {            let i: i32 = i.try_into().unwrap();            let pos = if let Some(p) = map.get(&c) {                p.clone()            } else {                -1            };            map.insert(c.clone(), i.clone());            if i - pos > cur {                cur = cur + 1;            } else {                cur = i - pos;            }            if res < cur {                res = cur;            }        }        res    }}