Given a string S
, return the number of substrings of length K
with no repeated characters.
Example 1:
Input: S = "havefunonleetcode", K = 5 Output: 6 Explanation: There are 6 substrings they are : 'havef','avefu','vefun','efuno','etcod','tcode'.
Example 2:
Input: S = "home", K = 5 Output: 0 Explanation: Notice K can be larger than the length of S. In this case is not possible to find any substring.
Note:
1 <= S.length <= 10^4
1 <= K <= 10^4
struct Solution;
use std::collections::HashMap;
impl Solution {
fn num_k_len_substr_no_repeats(s: String, k: i32) -> i32 {
let k = k as usize;
if s.len() < k {
return 0;
}
let mut hm: HashMap<char, usize> = HashMap::new();
let mut res = 0;
let s: Vec<char> = s.chars().collect();
let n = s.len();
for i in 0..n {
let ci = s[i];
*hm.entry(ci).or_default() += 1;
if i >= k {
let j = i - k;
let cj = s[j];
*hm.entry(cj).or_default() -= 1;
}
if hm.values().filter(|&v| *v == 1).sum::<usize>() == k {
res += 1;
}
}
res
}
}
#[test]
fn test() {
let s = "havefunonleetcode".to_string();
let k = 5;
let res = 6;
assert_eq!(Solution::num_k_len_substr_no_repeats(s, k), res);
let s = "home".to_string();
let k = 5;
let res = 0;
assert_eq!(Solution::num_k_len_substr_no_repeats(s, k), res);
}