LeetCode 3448 - Count Substrings Divisible By Last Digit

We are given a string s consisting only of decimal digits. Every substring of s represents a non-negative integer, and leading zeros are allowed. For each substring, we look at its last digit.

leetcodehardstringdynamic-programming

LeetCode Problem 3448

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

LeetCode 3448 - Count Substrings Divisible By Last Digit

Problem Understanding

We are given a string s consisting only of decimal digits. Every substring of s represents a non-negative integer, and leading zeros are allowed.

For each substring, we look at its last digit. If the last digit is non-zero, we check whether the numeric value of the substring is divisible by that last digit. If it is, the substring contributes 1 to the answer.

Our task is to count how many substrings satisfy this property.

For example, if a substring is "128", its last digit is 8, so we check whether 128 % 8 == 0. Since it is divisible, this substring is counted.

The constraints are important:

  • 1 <= s.length <= 100000
  • s contains only digits

A string of length 100000 contains roughly 5 * 10^9 substrings, so it is impossible to examine every substring individually. Any solution that explicitly generates substrings will be far too slow.

Several edge cases deserve attention:

  • Substrings may begin with one or more zeros.
  • Substrings ending with '0' must never be counted because the last digit must be non-zero.
  • Very large substrings cannot be converted into integers directly because their values may contain tens of thousands of digits.
  • The solution must process the string incrementally using modular arithmetic rather than constructing actual numbers.

Approaches

Brute Force

The most direct approach is to generate every substring.

For each starting position i and ending position j, we compute the integer represented by s[i:j+1], determine its last digit, and check divisibility.

This is correct because it literally follows the definition of the problem.

However, there are O(n²) substrings. Even if divisibility checking were constant time, this would already be far too slow for n = 100000. In practice, converting large substrings into integers makes it even worse.

Key Insight

The last digit of any valid substring must be one of 1 through 9.

Instead of examining every substring separately, we process the string from left to right and maintain information about all substrings ending at the current position.

Suppose we want to know, for some modulus k, how many substrings ending at the current position have each possible remainder modulo k.

When a new digit x is appended:

new_value = old_value * 10 + x

Therefore:

new_remainder = (old_remainder * 10 + x) % k

This means every existing remainder can be updated efficiently without reconstructing the actual number.

Since the last digit can only be one of 1..9, we only need to track remainders for moduli 1 through 9.

For every position:

  1. Update remainder distributions for all moduli 1..9.
  2. Let the current digit be d.
  3. If d != 0, every substring ending here whose remainder modulo d equals 0 contributes to the answer.

Because there are only nine possible moduli, the total work per character is constant.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) or worse O(1) Enumerates all substrings
Optimal O(n) O(1) Tracks remainder counts for moduli 1 through 9

Algorithm Walkthrough

  1. Create remainder-count tables for every modulus from 1 to 9.

For a modulus k, maintain an array of size k.

dp[k][r]

represents the number of substrings ending at the previous position whose value modulo k equals r. 2. Process the string from left to right.

Let the current digit be x. 3. For every modulus k from 1 to 9, construct a new remainder table.

Every previously tracked substring can be extended by digit x.

If a substring previously had remainder r, its new remainder becomes

(r * 10 + x) % k

Add the corresponding count into the new table. 4. Also create the single-character substring consisting only of digit x.

Its remainder is

x % k

Increase that remainder count by one. 5. Replace the old table with the newly constructed table.

At this point, the table describes all substrings ending at the current position. 6. Let the current digit be d.

If d == 0, no substring ending here can contribute because the problem requires a non-zero last digit. 7. Otherwise, every substring ending here that has remainder 0 modulo d is valid.

Add

dp[d][0]

to the answer. 8. Continue until the entire string has been processed.

Why it works

For every modulus k, the algorithm maintains an exact count of all substrings ending at the current position grouped by their remainder modulo k.

The transition

new_remainder = (old_remainder * 10 + digit) % k

is exactly the modular arithmetic rule for appending a decimal digit. Therefore, after processing a position, dp[k][r] accurately counts substrings ending there with remainder r.

When the current last digit is d, a substring is divisible by its last digit precisely when its remainder modulo d is zero. Thus dp[d][0] counts exactly the valid substrings ending at that position. Summing this quantity over all positions gives the correct answer.

Python Solution

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [None] * 10

        for k in range(1, 10):
            dp[k] = [0] * k

        answer = 0

        for ch in s:
            digit = int(ch)

            new_dp = [None] * 10

            for k in range(1, 10):
                curr = [0] * k

                for remainder, count in enumerate(dp[k]):
                    if count:
                        new_remainder = (remainder * 10 + digit) % k
                        curr[new_remainder] += count

                curr[digit % k] += 1
                new_dp[k] = curr

            dp = new_dp

            if digit != 0:
                answer += dp[digit][0]

        return answer

The implementation stores one remainder-frequency table for each modulus from 1 through 9.

For every incoming digit, a fresh table is built. Each existing remainder state is extended using the standard decimal append formula:

(remainder * 10 + digit) % k

After extending all previous substrings, the code inserts the new single-character substring.

Once all tables have been updated, the current digit determines which modulus matters. If the digit is non-zero, the count of remainder-zero substrings for that modulus is added directly to the answer.

Because the largest modulus is only 9, the amount of work per character remains constant.

Go Solution

func countSubstrings(s string) int64 {
	dp := make([][]int64, 10)

	for k := 1; k <= 9; k++ {
		dp[k] = make([]int64, k)
	}

	var answer int64

	for _, ch := range s {
		digit := int(ch - '0')

		newDP := make([][]int64, 10)

		for k := 1; k <= 9; k++ {
			curr := make([]int64, k)

			for rem, cnt := range dp[k] {
				if cnt == 0 {
					continue
				}

				newRem := (rem*10 + digit) % k
				curr[newRem] += cnt
			}

			curr[digit%k]++
			newDP[k] = curr
		}

		dp = newDP

		if digit != 0 {
			answer += dp[digit][0]
		}
	}

	return answer
}

The Go implementation follows exactly the same state transition as the Python version.

One notable difference is that the answer can be as large as the number of substrings, which is approximately n(n+1)/2. For n = 100000, this exceeds the range of a 32-bit integer, so int64 is used for all counts and for the final answer.

Worked Examples

Example 1

Input:

s = "12936"

The following table shows the contribution added at each position.

Position Digit Valid substrings ending here Added
0 1 "1" 1
1 2 "2", "12" 2
2 9 "9", "129" 2
3 3 "3", "93", "1293" 3
4 6 "6", "36", "936" 3

Total:

1 + 2 + 2 + 3 + 3 = 11

Answer:

11

Example 2

Input:

s = "5701283"

The algorithm processes digits one by one and continuously maintains remainder distributions for moduli 1..9.

The contributions at each ending position are:

Position Digit Added
0 5 1
1 7 1
2 0 0
3 1 4
4 2 4
5 8 3
6 3 5

Total:

18

Example 3

Input:

s = "1010101010"

Only substrings ending in digit 1 can contribute.

Every substring ending in 0 is ignored because the last digit must be non-zero.

The positions containing '1' are:

0, 2, 4, 6, 8

For each such position, every substring ending there is divisible by 1.

The number of substrings ending at these positions is:

1 + 3 + 5 + 7 + 9 = 25

Answer:

25

Complexity Analysis

Measure Complexity Explanation
Time O(n) Nine moduli, each with at most nine remainders
Space O(1) Only fixed-size remainder tables are stored

The total number of remainder states is:

1 + 2 + 3 + ... + 9 = 45

For every character, the algorithm updates these 45 states. Since this number is constant, the running time grows linearly with the length of the string. The memory usage is also constant because the state size never depends on n.

Test Cases

sol = Solution()

assert sol.countSubstrings("12936") == 11      # example 1
assert sol.countSubstrings("5701283") == 18    # example 2
assert sol.countSubstrings("1010101010") == 25 # example 3

assert sol.countSubstrings("1") == 1           # single non-zero digit
assert sol.countSubstrings("0") == 0           # single zero digit

assert sol.countSubstrings("11") == 3          # all substrings divisible by 1
assert sol.countSubstrings("22") == 3          # 2, 2, 22

assert sol.countSubstrings("10") == 1          # trailing zero ignored
assert sol.countSubstrings("01") == 2          # leading zero substring allowed

assert sol.countSubstrings("999") == 6         # every substring divisible by 9
assert sol.countSubstrings("333") == 6         # every substring divisible by 3

assert sol.countSubstrings("12345") == 11      # mixed digits
assert sol.countSubstrings("1000") == 1        # only the first digit contributes

assert sol.countSubstrings("00000") == 0       # all zeros
assert sol.countSubstrings("11111") == 15      # every substring valid

# larger stress-style pattern
assert sol.countSubstrings("10101") == 9

Test Summary

Test Why
"12936" Official example
"5701283" Official example
"1010101010" Official example with many zeros
"1" Smallest valid non-zero input
"0" Smallest zero-only input
"11" Every substring valid
"22" Checks divisibility by 2
"10" Ending zero must not count
"01" Leading zeros are allowed
"999" Divisibility by 9
"333" Divisibility by 3
"12345" General mixed case
"1000" One valid substring followed by zeros
"00000" All substrings invalid
"11111" Maximum density of valid substrings
"10101" Alternating zero and non-zero digits

Edge Cases

Substrings Ending With Zero

A common mistake is to test divisibility by the last digit even when that digit is zero. Division by zero is undefined, and the problem explicitly requires a non-zero last digit.

The implementation handles this by checking:

if digit != 0:
    answer += dp[digit][0]

No contribution is added when the current digit is zero.

Leading Zeros

Substrings such as "01" and "0008" are completely valid. Their numerical values are still interpreted normally as 1 and 8.

Because the algorithm works purely with modular arithmetic and never strips leading zeros, these substrings are processed correctly without any special handling.

Very Large Substrings

A substring may contain tens of thousands of digits. Converting such a substring into an integer would be infeasible.

The solution never stores actual numeric values. It only stores remainders modulo 1..9, which are always small. This avoids overflow and keeps the algorithm efficient even for the maximum input size.

Maximum Input Length

With n = 100000, any quadratic algorithm will time out.

The dynamic programming state contains only 45 remainder buckets in total, regardless of input length. Consequently, the algorithm remains linear and easily handles the largest allowed strings.