Code shared from the Rust Playground

playground.rs

// https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters

// Note this is a subscribe problem

//    Good morning! Here's your coding interview problem for today.
//
//    This problem was asked by Amazon.
//
//    Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.
//
//    For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".
use std::collections::HashMap;
pub struct Solution {}
impl Solution {
    pub fn longest_substr_with_at_most_k_distinct_chars(s: String, k: usize) -> String {
        // this is a sliding window algorithm
        if s.is_empty() || k == 0 {
            return String::from("");
        }

        // keys are chars, values are indices when first seen
        let mut seen_chars = HashMap::new();
        let mut earliest_seen_char = None;
        let mut longest_substr_start = 0;
        let mut longest_substr_end = 0;

        // these values will keep track of the current string being looked at
        let mut start = 0;
        let mut end = 0;

        for (i, c) in s.chars().enumerate() {
            if !seen_chars.contains_key(&c) {
                if seen_chars.len() < k {
                    seen_chars.insert(c, i);
                } else {
                    if earliest_seen_char.is_some() {
                        start = seen_chars.remove(earliest_seen_char.unwrap()).unwrap();
                        seen_chars.insert(c, i);
                    } else {
                        earliest_seen_char = Some(&c);
                        seen_chars.insert(c, i);
                    }
                }
            } else {
                end = i;
                if end - start > longest_substr_end - longest_substr_start {
                    longest_substr_start = start;
                    longest_substr_end = end;
                }
            }
        }

        s.get(longest_substr_start..longest_substr_end).unwrap().to_string()
    }
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn n0340_1() {
        assert_eq!(String::from("bcb"), Solution::longest_substr_with_at_most_k_distinct_chars(String::from("abcba"), 2));
    }
}