Count substrings divisible by last digit

String Dynamic Programming

22.9% acceptance

Feb 25, 2026

You are given a string s consisting of digits. Return the number of substrings of s divisible by their non-zero last digit. Note: A substring may contain leading zeros.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_substrings(s: String) -> i64 {
    let digits: Vec<usize> = s.bytes().map(|b| (b - b'0') as usize).collect();
    let n = digits.len();
    let mut ans = 0i64;
    // cnt[d][rem] = number of substrings ending at previous position with value ≡ rem (mod d)
    // d = 1..9, size of cnt[d] = d
    let mut cnt: Vec<Vec<i64>> = (0..=9).map(|d| if d == 0 { vec![] } else { vec![0i64; d] }).collect();
    for r in 0..n {
      let dig = digits[r];
      // Update cnt[d] for ALL d = 1..9
      for d in 1..=9usize {
        let mut new_cnt = vec![0i64; d];
        // Transform existing substrings: value -> value*10 + dig
        for rem in 0..d {
          if cnt[d][rem] == 0 { continue; }
          let new_rem = (rem * 10 + dig) % d;
          new_cnt[new_rem] += cnt[d][rem];
        }
        // Add new single-element substring (value = dig)
        new_cnt[dig % d] += 1;
        cnt[d] = new_cnt;
      }
      // Count substrings ending at r that are divisible by their last digit
      if dig != 0 {
        ans += cnt[dig][0];
      }
    }
    ans
  }
}