LeetCode 3448: Count Substrings Divisible By Last Digit (DP by Divisor 1..9)
LeetCode 3448DPRemainderMathToday we solve LeetCode 3448 - Count Substrings Divisible By Last Digit.
Source: https://leetcode.com/problems/count-substrings-divisible-by-last-digit/
English
Problem Summary
Given a digit string s, count substrings whose numeric value is divisible by its last digit.
If the last digit is 0, that substring does not contribute because division by zero is invalid.
Key Insight
At position i, the divisor is fixed as d = s[i] (1..9).
We only need the number of substrings ending at i with value modulo d equal to 0.
So we maintain DP for every divisor d = 1..9:
dp[d][r] = number of substrings ending at current position whose value % d == r.
When appending a digit x, remainders transition as:
newR = (oldR * 10 + x) % d.
Algorithm
1) Initialize 9 remainder tables (for divisors 1..9).
2) Scan each digit x in s.
3) For each divisor d, build next table by extending all old substrings and starting a new single-digit substring.
4) Replace current table with next table.
5) If x != 0, add dp[x][0] to answer.
Complexity Analysis
For each character, we process divisors 1..9 and at most d remainders per divisor.
Time: O(n * 45) (constant factor, effectively linear).
Space: O(45) for all remainder states.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public long countSubstrings(String s) {
long[][] dp = new long[10][];
for (int d = 1; d <= 9; d++) dp[d] = new long[d];
long ans = 0L;
for (int i = 0; i < s.length(); i++) {
int x = s.charAt(i) - '0';
for (int d = 1; d <= 9; d++) {
long[] next = new long[d];
for (int r = 0; r < d; r++) {
long cnt = dp[d][r];
if (cnt == 0) continue;
int nr = (r * 10 + x) % d;
next[nr] += cnt;
}
next[x % d] += 1; // single digit substring
dp[d] = next;
}
if (x != 0) ans += dp[x][0];
}
return ans;
}
}func countSubstrings(s string) int64 {
dp := make([][]int64, 10)
for d := 1; d <= 9; d++ {
dp[d] = make([]int64, d)
}
var ans int64 = 0
for i := 0; i < len(s); i++ {
x := int(s[i] - '0')
for d := 1; d <= 9; d++ {
next := make([]int64, d)
for r := 0; r < d; r++ {
cnt := dp[d][r]
if cnt == 0 {
continue
}
nr := (r*10 + x) % d
next[nr] += cnt
}
next[x%d] += 1
dp[d] = next
}
if x != 0 {
ans += dp[x][0]
}
}
return ans
}class Solution {
public:
long long countSubstrings(string s) {
vector<vector<long long>> dp(10);
for (int d = 1; d <= 9; ++d) dp[d] = vector<long long>(d, 0);
long long ans = 0;
for (char ch : s) {
int x = ch - '0';
for (int d = 1; d <= 9; ++d) {
vector<long long> next(d, 0);
for (int r = 0; r < d; ++r) {
long long cnt = dp[d][r];
if (cnt == 0) continue;
int nr = (r * 10 + x) % d;
next[nr] += cnt;
}
next[x % d] += 1;
dp[d].swap(next);
}
if (x != 0) ans += dp[x][0];
}
return ans;
}
};class Solution:
def countSubstrings(self, s: str) -> int:
dp = [None] * 10
for d in range(1, 10):
dp[d] = [0] * d
ans = 0
for ch in s:
x = ord(ch) - ord('0')
for d in range(1, 10):
nxt = [0] * d
for r, cnt in enumerate(dp[d]):
if cnt == 0:
continue
nr = (r * 10 + x) % d
nxt[nr] += cnt
nxt[x % d] += 1
dp[d] = nxt
if x != 0:
ans += dp[x][0]
return ansvar countSubstrings = function(s) {
const dp = new Array(10);
for (let d = 1; d <= 9; d++) {
dp[d] = new Array(d).fill(0);
}
let ans = 0;
for (let i = 0; i < s.length; i++) {
const x = s.charCodeAt(i) - 48;
for (let d = 1; d <= 9; d++) {
const next = new Array(d).fill(0);
for (let r = 0; r < d; r++) {
const cnt = dp[d][r];
if (cnt === 0) continue;
const nr = (r * 10 + x) % d;
next[nr] += cnt;
}
next[x % d] += 1;
dp[d] = next;
}
if (x !== 0) {
ans += dp[x][0];
}
}
return ans;
};中文
题目概述
给定数字字符串 s，统计所有满足条件的子串：子串对应的数值可以被其最后一位数字整除。
如果最后一位是 0，由于不能除以 0，该子串不计入答案。
核心思路
对于每个结尾位置 i，分母已经固定为 d = s[i]（1..9）。
因此我们只需知道“以 i 结尾的子串里，有多少个对 d 取模为 0”。
维护 9 组 DP（对应 d=1..9）：
dp[d][r] 表示“当前结尾下，值 % d == r 的子串数量”。
当追加新数字 x 时，余数转移为：
newR = (oldR * 10 + x) % d。
算法步骤
1）初始化 d=1..9 的余数计数数组。
2）从左到右扫描每个数字 x。
3）对每个 d，枚举旧余数并完成转移，同时加入长度为 1 的新子串。
4）用新数组替换旧数组。
5）若 x != 0，把 dp[x][0] 加入总答案。
复杂度分析
每个字符会处理 d=1..9 且每个 d 只遍历 0..d-1 的余数。
时间复杂度：O(n * 45)（常数很小，可视为线性）。
空间复杂度：O(45)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public long countSubstrings(String s) {
long[][] dp = new long[10][];
for (int d = 1; d <= 9; d++) dp[d] = new long[d];
long ans = 0L;
for (int i = 0; i < s.length(); i++) {
int x = s.charAt(i) - '0';
for (int d = 1; d <= 9; d++) {
long[] next = new long[d];
for (int r = 0; r < d; r++) {
long cnt = dp[d][r];
if (cnt == 0) continue;
int nr = (r * 10 + x) % d;
next[nr] += cnt;
}
next[x % d] += 1;
dp[d] = next;
}
if (x != 0) ans += dp[x][0];
}
return ans;
}
}func countSubstrings(s string) int64 {
dp := make([][]int64, 10)
for d := 1; d <= 9; d++ {
dp[d] = make([]int64, d)
}
var ans int64 = 0
for i := 0; i < len(s); i++ {
x := int(s[i] - '0')
for d := 1; d <= 9; d++ {
next := make([]int64, d)
for r := 0; r < d; r++ {
cnt := dp[d][r]
if cnt == 0 {
continue
}
nr := (r*10 + x) % d
next[nr] += cnt
}
next[x%d] += 1
dp[d] = next
}
if x != 0 {
ans += dp[x][0]
}
}
return ans
}class Solution {
public:
long long countSubstrings(string s) {
vector<vector<long long>> dp(10);
for (int d = 1; d <= 9; ++d) dp[d] = vector<long long>(d, 0);
long long ans = 0;
for (char ch : s) {
int x = ch - '0';
for (int d = 1; d <= 9; ++d) {
vector<long long> next(d, 0);
for (int r = 0; r < d; ++r) {
long long cnt = dp[d][r];
if (cnt == 0) continue;
int nr = (r * 10 + x) % d;
next[nr] += cnt;
}
next[x % d] += 1;
dp[d].swap(next);
}
if (x != 0) ans += dp[x][0];
}
return ans;
}
};class Solution:
def countSubstrings(self, s: str) -> int:
dp = [None] * 10
for d in range(1, 10):
dp[d] = [0] * d
ans = 0
for ch in s:
x = ord(ch) - ord('0')
for d in range(1, 10):
nxt = [0] * d
for r, cnt in enumerate(dp[d]):
if cnt == 0:
continue
nr = (r * 10 + x) % d
nxt[nr] += cnt
nxt[x % d] += 1
dp[d] = nxt
if x != 0:
ans += dp[x][0]
return ansvar countSubstrings = function(s) {
const dp = new Array(10);
for (let d = 1; d <= 9; d++) {
dp[d] = new Array(d).fill(0);
}
let ans = 0;
for (let i = 0; i < s.length; i++) {
const x = s.charCodeAt(i) - 48;
for (let d = 1; d <= 9; d++) {
const next = new Array(d).fill(0);
for (let r = 0; r < d; r++) {
const cnt = dp[d][r];
if (cnt === 0) continue;
const nr = (r * 10 + x) % d;
next[nr] += cnt;
}
next[x % d] += 1;
dp[d] = next;
}
if (x !== 0) {
ans += dp[x][0];
}
}
return ans;
};
Comments