Count Substrings Divisible By Last Digit

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.

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.

1class Solution {2    public int countSubstrings(String s) {3        int n = s.length();4        long count = 0;5        for (int j = 0; j < n; j++) {6            int lastDigit = s.charAt(j) - '0';7            if (lastDigit == 0) {8                continue;9            }10 11            long currentNumRem = 0;12            long powerOf10 = 1;13            // Iterate through all substrings ending at j14            for (int i = j; i >= 0; i--) {15                int digit = s.charAt(i) - '0';16                17                // Calculate the number represented by s[i..j] modulo lastDigit18                // We build the number from right to left (from s[j] to s[i])19                currentNumRem = (currentNumRem + (long)digit * powerOf10) % lastDigit;20                if (currentNumRem == 0) {21                    count++;22                }23                powerOf10 = (powerOf10 * 10) % lastDigit;24            }25        }26        return (int)count;27    }28}

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.

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.

1class Solution {2    public int countSubstrings(String s) {3        int n = s.length();4        long totalCount = 0;5        // dp[d][rem] = count of substrings ending at the *previous* position6        // with remainder rem when divided by d.7        long[][] dp = new long[10][10];8 9        for (int i = 0; i < n; i++) {10            int digit = s.charAt(i) - '0';11            long[][] newDp = new long[10][10];12 13            // Update DP states for all possible divisors14            for (int d = 1; d <= 9; d++) {15                // Case 1: Substrings formed by appending the current digit16                // to substrings ending at the previous position.17                for (int rem = 0; rem < d; rem++) {18                    int newRem = (rem * 10 + digit) % d;19                    newDp[d][newRem] += dp[d][rem];20                }21                // Case 2: The new single-digit substring s[i].22                newDp[d][digit % d]++;23            }24            25            dp = newDp;26 27            if (digit != 0) {28                // Add the count of substrings ending at i that are divisible by `digit`.29                // This is the count of substrings with remainder 0 for divisor `digit`.30                totalCount += dp[digit][0];31            }32        }33        // The problem's return type is int, so we cast.34        return (int) totalCount;35    }36}