mod s0003_longest_substring_without_repeating_characters;

pub struct Solution {}

use std::collections::{HashSet, HashMap};

impl Solution {

pub fn length_of_longest_substring(s: String) -> i32 {

let mut start = 0;

let mut max_substr_len = 0;

let mut occurrence_map = HashSet::with_capacity(s.len());

let mut chr_idx_map = HashMap::with_capacity(s.len());

// Don't consider Unicode Strings (related with graphemes)

for (idx, chr) in s.chars().enumerate() {

// Make substring that ends with (idx, chr)

// (0) String preprocessing to make further O(1) string indexing

chr_idx_map.insert(idx, chr);

// (1) If s[idx] exists in substring s[start:idx-1], keep removing first char of s[start:idx-1] until there is no s[idx]

while occurrence_map.contains(&chr) {

assert!(start < idx);

let fst_chr = chr_idx_map.get(&start).unwrap();

occurrence_map.remove(fst_chr);

start += 1;

}

// (2) Now substring s[start:idx] doesn't contain repeating character. Update occurrence_map.

occurrence_map.insert(chr);

// (3) update max_len

let new_substr_len = idx - start + 1;

max_substr_len = if new_substr_len >= max_substr_len { new_substr_len } else { max_substr_len };

}

max_substr_len as i32

}

mod tests {

use super::*;

#[test]

fn test_3() {

assert_eq!(Solution::length_of_longest_substring(String::from("abcabcbb")), 3);

assert_eq!(Solution::length_of_longest_substring(String::from("bbbbb")), 1);

assert_eq!(Solution::length_of_longest_substring(String::from("pwwkew")), 3);

assert_eq!(Solution::length_of_longest_substring(String::from("a")), 1);

}