Number of divisible substrings

Hash Table String Counting Prefix Sum

74.6% acceptance

Mar 31, 2026

Each character of the English alphabet has been mapped to a digit as shown below. A string is divisible if the sum of the mapped values of its characters is divisible by its length. Given a string s, return the number of divisible substrings of s. A substring is a contiguous non-empty sequence of characters within a string.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_divisible_substrings(word: String) -> i32 {
    let map = |c: u8| -> i32 {
      match c {
        b'a' | b'b' => 1,
        b'c' | b'd' | b'e' => 2,
        b'f' | b'g' | b'h' => 3,
        b'i' | b'j' | b'k' => 4,
        b'l' | b'm' | b'n' => 5,
        b'o' | b'p' | b'q' => 6,
        b'r' | b's' | b't' => 7,
        b'u' | b'v' | b'w' => 8,
        b'x' | b'y' | b'z' => 9,
        _ => 0,
      }
    };
    let bytes: Vec<i32> = word.bytes().map(|b| map(b)).collect();
    let n = bytes.len();
    let mut count = 0;
    for i in 0..n {
      let mut sum = 0;
      for j in i..n {
        sum += bytes[j];
        let len = (j - i + 1) as i32;
        if sum % len == 0 {
          count += 1;
        }
      }
    }
    count
  }
}