Count residue prefixes

Hash Table String

65.4% acceptance

Mar 16, 2026

You are given a string s consisting only of lowercase English letters. A prefix of s is called a residue if the number of distinct characters in the prefix is equal to len(prefix) % 3. Return the count of residue prefixes in s. A prefix of a string is a non-empty substring that starts from the beginning of the string and extends to any point within it.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn residue_prefixes(s: String) -> i32 {
    let bytes = s.as_bytes();
    let mut seen = [false; 26];
    let mut distinct = 0u32;
    let mut count = 0;

    for (i, &b) in bytes.iter().enumerate() {
      let c = (b - b'a') as usize;
      if !seen[c] {
        seen[c] = true;
        distinct += 1;
      }
      let len_mod3 = ((i + 1) % 3) as u32;
      if distinct == len_mod3 {
        count += 1;
      }
    }

    count
  }
}