Count substrings without repeating character

Hash Table String Sliding Window

75.9% acceptance

Mar 31, 2026

You are given a string s consisting only of lowercase English letters. We call a substring special if it contains no character which has occurred at least twice (in other words, it does not contain a repeating character). Your task is to count the number of special substrings. For example, in the string "pop", the substring "po" is a special substring, however, "pop" is not special (since 'p' has occurred twice). Return the number of special substrings. A substring is a contiguous sequence of characters within a string. For example, "abc" is a substring of "abcd", but "acd" is not.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_special_substrings(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    let mut count = [0i32; 26];
    let mut left = 0;
    let mut result = 0i32;
    for right in 0..n {
      count[(s[right] - b'a') as usize] += 1;
      while count[(s[right] - b'a') as usize] > 1 {
        count[(s[left] - b'a') as usize] -= 1;
        left += 1;
      }
      result += (right - left + 1) as i32;
    }
    result
  }
}