LeetCode #3: Longest Substring Without Repeating Characters

My task today, as suggested by the title, is to find the longest substring without repeating characters. The challenge appears to be quite easy.

My initial approach is to iterate through every character, processing them one by one while keeping track of the sequence. When I see a character that already exists in the list, I trim the sequence’s beginning, to make a room for a new character. It reminds me snake game I played as a child.

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut longest: usize = 0;
        let mut current: Vec<char> = Vec::new();

        for c in s.chars() {
            if let Some(index) = current.iter().position(|&x| x == c) {
                longest = std::cmp::max(current.len(), longest);

                for i in 0..=index {
                    current.remove(0);
                }
            }

            current.push(c);
        }

        std::cmp::max(current.len(), longest) as i32
    }
}

After the first submission I had a second thought: Why at all do I keep track of the substring? I noticed I can just track the index of the first character in the currently longest substring. I ended up with such code:

use std::collections::HashMap;

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut start: usize = 0;
        let mut longest: usize = 0;
        let mut indices: HashMap<char, usize> = HashMap::new();

        for (index, character) in s.chars().enumerate() {
            if let Some(found) = indices.get(&character) {
                start = std::cmp::max(start, found + 1);
            }

            longest = std::cmp::max(index - start + 1, longest);
            indices.insert(character, index);
        }

        std::cmp::max(s.len() - start, longest) as i32
    }
}

I have two reflections after this challenge:

• The platform doesn’t generate Rust friendly types like usize for returned value. It pushes me do ugly casting.
• The improvement of the algorithm decreased the performance measured by the platform. The HashMap introduced some overhead for such small dataset.

https://leetcode.com/problems/longest-substring-without-repeating-characters/