# Count Substrings Divisible By Last Digit
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-substrings-divisible-by-last-digit)
Canonical: https://scaleengineer.com/dsa/problems/count-substrings-divisible-by-last-digit
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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.

**Example 1:**

**Input:** s = "12936"

**Output:** 11

**Explanation:**

Substrings `"29"`, `"129"`, `"293"` and `"2936"` are not divisible by their last digit. There are 15 substrings in total, so the answer is `15 - 4 = 11`.

**Example 2:**

**Input:** s = "5701283"

**Output:** 18

**Explanation:**

Substrings `"01"`, `"12"`, `"701"`, `"012"`, `"128"`, `"5701"`, `"7012"`, `"0128"`, `"57012"`, `"70128"`, `"570128"`, and `"701283"` are all divisible by their last digit. Additionally, all substrings that are just 1 non-zero digit are divisible by themselves. Since there are 6 such digits, the answer is `12 + 6 = 18`.

**Example 3:**

**Input:** s = "1010101010"

**Output:** 25

**Explanation:**

Only substrings that end with digit `'1'` are divisible by their last digit. There are 25 such substrings.

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of digits only.

# Approaches
## Brute-force with Modular Arithmetic
This approach iterates through all possible substrings of the given string `s`. For each substring, it checks if it's divisible by its last digit. To handle potentially very large numbers represented by substrings, it uses modular arithmetic to calculate the remainder efficiently, thus avoiding overflow issues with standard integer types.
**Time:** O(n^2) - There are two nested loops. The outer loop runs `n` times (for the end position `j`), and the inner loop runs `j+1` times (for the start position `i`). This results in a quadratic time complexity. · **Space:** O(1) - We only use a few variables to store the count and intermediate values for the modular arithmetic calculation, regardless of the input size.
**Pros:** Relatively simple to understand and implement.; Correctly handles arbitrarily large numbers by using modular arithmetic, avoiding overflow.; Requires minimal extra space.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n up to 10^5), and this solution will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode.
### Explanation
The algorithm uses a nested loop structure to generate all substrings. The outer loop fixes the ending character of the substring, and the inner loop iterates backwards to define the starting character.

For a substring ending at index `j`, the last digit is `d = s.charAt(j) - '0'`. We are interested in counting how many start indices `i <= j` result in the number represented by `s[i..j]` being divisible by `d`.

Instead of converting the substring to a number directly (which can be very large), we calculate its value modulo `d` on the fly. As we iterate from `i = j` down to `0`, we build the number from right to left, keeping track of the running remainder and the corresponding power of 10. If the final remainder for a substring `s[i..j]` is 0, we've found a valid substring and increment our counter.

```java
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        long count = 0;
        for (int j = 0; j < n; j++) {
            int lastDigit = s.charAt(j) - '0';
            if (lastDigit == 0) {
                continue;
            }

            long currentNumRem = 0;
            long powerOf10 = 1;
            // Iterate through all substrings ending at j
            for (int i = j; i >= 0; i--) {
                int digit = s.charAt(i) - '0';
                
                // Calculate the number represented by s[i..j] modulo lastDigit
                // We build the number from right to left (from s[j] to s[i])
                currentNumRem = (currentNumRem + (long)digit * powerOf10) % lastDigit;
                if (currentNumRem == 0) {
                    count++;
                }
                powerOf10 = (powerOf10 * 10) % lastDigit;
            }
        }
        return (int)count;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Iterate through the string with an index `j` from `0` to `n-1`, where `j` represents the ending position of a substring.
3. For each `j`, get the last digit `d = s.charAt(j) - '0'`. If `d` is 0, continue to the next `j` since division by zero is not allowed.
4. For the fixed ending position `j` and last digit `d`, iterate with an index `i` from `j` down to `0`. This `i` represents the starting position of the substring.
5. For each substring `s[i..j]`, we need to calculate the number it represents modulo `d`. To do this without causing an overflow with large numbers, we compute it iteratively.
6. Inside the inner loop (for `i`), we build the number from right to left. We maintain the `currentNumRem` (remainder of the number formed by `s[i..j]`) and the current `powerOf10`, both modulo `d`.
7. In each step of the inner loop, we update `currentNumRem` by adding the contribution of the current digit `s[i]`. The formula is `currentNumRem = (currentNumRem + (s.charAt(i) - '0') * powerOf10) % d`.
8. If `currentNumRem` becomes 0, it means the number represented by `s[i..j]` is divisible by `d`, so we increment `count`.
9. We also update `powerOf10` for the next digit to the left: `powerOf10 = (powerOf10 * 10) % d`.
10. After all loops complete, `count` will hold the total number of such substrings.

## Dynamic Programming with Remainder Counts
A more efficient solution uses dynamic programming. We can process the string from left to right, and at each position `i`, we calculate the number of valid substrings that end at `i`. To do this efficiently, we maintain DP states that keep track of remainder counts for all possible divisors (1 through 9).
**Time:** O(n) - The algorithm iterates through the string once. The work inside the loop is constant because the nested loops for divisors `d` and remainders `rem` run a fixed number of times (at most `1+2+...+9 = 45` inner operations per `d`-loop). · **Space:** O(1) - The DP table `dp` has a fixed size of `10x10`, which is constant and does not depend on the length of the input string `n`.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Systematically handles all divisors without needing complex, separate logic for each divisibility rule.; Uses constant extra space, as the DP table size is fixed.
**Cons:** The logic is more abstract and can be harder to understand initially compared to a direct brute-force approach.
### Explanation
The core idea is to build up the solution by iterating through the string once. For each character `s[i]`, we want to know how many substrings ending at `i` are divisible by the digit `s[i]`. A substring ending at `i`, say `s[k..i]`, is formed by appending `s[i]` to a substring ending at `i-1` (i.e., `s[k..i-1]`), or it's the single-digit substring `s[i]`.

The remainder of the new number `N(k,i)` modulo some divisor `d` can be calculated from the remainder of `N(k,i-1)`: `N(k,i) % d = ( (N(k,i-1) % d) * 10 + (s[i]-'0') ) % d`.

This suggests a DP approach. We maintain a table `dp[d][rem]` which stores the count of substrings ending at the *previous* position `i-1` having a remainder `rem` when divided by `d`. We do this for all possible non-zero last digits `d` from 1 to 9.

When we are at position `i`, we compute a new DP table based on the previous one. For each divisor `d`, we transition the counts based on the formula above. We also add 1 for the new single-digit substring `s[i]`. After computing the DP table for the current position `i`, the number of valid substrings ending at `i` is simply the count of substrings with remainder 0 when divided by `s[i] - '0'`. We add this to our total count.

```java
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        long totalCount = 0;
        // dp[d][rem] = count of substrings ending at the *previous* position
        // with remainder rem when divided by d.
        long[][] dp = new long[10][10];

        for (int i = 0; i < n; i++) {
            int digit = s.charAt(i) - '0';
            long[][] newDp = new long[10][10];

            // Update DP states for all possible divisors
            for (int d = 1; d <= 9; d++) {
                // Case 1: Substrings formed by appending the current digit
                // to substrings ending at the previous position.
                for (int rem = 0; rem < d; rem++) {
                    int newRem = (rem * 10 + digit) % d;
                    newDp[d][newRem] += dp[d][rem];
                }
                // Case 2: The new single-digit substring s[i].
                newDp[d][digit % d]++;
            }
            
            dp = newDp;

            if (digit != 0) {
                // Add the count of substrings ending at i that are divisible by `digit`.
                // This is the count of substrings with remainder 0 for divisor `digit`.
                totalCount += dp[digit][0];
            }
        }
        // The problem's return type is int, so we cast.
        return (int) totalCount;
    }
}
```
### Algorithm
1. Initialize `totalCount = 0`.
2. Initialize a 2D array, `dp[10][10]`, where `dp[d][rem]` will store the count of substrings ending at the *current* position `i` that have a remainder of `rem` when divided by `d`.
3. Iterate through the string `s` from `i = 0` to `n-1`.
4. In each iteration, get the current `digit = s.charAt(i) - '0'`.
5. Create a temporary `newDp` table for the current position `i`. This is because the calculation for position `i` depends on the results from `i-1`.
6. For each possible divisor `d` from 1 to 9:
   a. Transition the counts from the previous state (`dp` table for position `i-1`) to the current state (`newDp` table for position `i`). For each previous remainder `r` from `0` to `d-1`, the `dp[d][r]` substrings are extended with the current `digit`. Their new remainder will be `(r * 10 + digit) % d`. We add `dp[d][r]` to `newDp[d][newRem]`.
   b. Account for the new single-digit substring `s[i]`. Increment `newDp[d][digit % d]` by 1.
7. After populating `newDp` for all divisors, update the main `dp` table: `dp = newDp`.
8. If the current `digit` is not zero, it is the last digit of all substrings ending at `i`. The number of these substrings that are divisible by `digit` is exactly the count we just computed for remainder 0, i.e., `dp[digit][0]`. Add this value to `totalCount`.
9. After the loop finishes, return `totalCount`.