LeetCode 2950 - Number of Divisible Substrings

The problem asks us to analyze a given string word where each lowercase English letter is mapped to a digit according to a classic phone keypad scheme.

leetcodemediumhash-tablestringcountingprefix-sum

LeetCode Problem 2950

Difficulty: 🟡 Medium
Topics: Hash Table, String, Counting, Prefix Sum

Solution

Problem Understanding

The problem asks us to analyze a given string word where each lowercase English letter is mapped to a digit according to a classic phone keypad scheme. A substring of the string is considered divisible if the sum of the mapped digits of its characters is divisible by the length of the substring. The task is to count all such divisible substrings.

The input is a string of length up to 2000 characters. Each substring is contiguous, and the problem requires counting all possible substrings that satisfy the divisibility condition. This includes single-character substrings, which are always divisible because any number is divisible by 1. The constraints suggest a brute-force solution examining all substrings would be O(n³) if done naively (because computing sums for all substrings directly requires O(n) per substring), which is too slow for n = 2000. The problem guarantees valid lowercase letters, so there is no need to handle invalid input.

Important edge cases include strings of length 1, strings where no substring is divisible beyond single characters, and strings where all characters are the same.

Approaches

The brute-force approach involves iterating over all possible substrings. For each substring, we calculate the sum of mapped digits and check divisibility by the substring length. This approach works because it directly implements the problem definition. However, computing the sum of each substring repeatedly is inefficient, giving a time complexity of O(n³), which is impractical for n up to 2000.

The optimal approach leverages prefix sums. By computing a prefix sum array where each element represents the sum of mapped digits up to that index, we can calculate the sum of any substring in O(1) time. For substring word[i:j], its sum is prefix[j] - prefix[i]. This reduces the total complexity to O(n²), which is feasible for n = 2000.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Compute sum of each substring separately and check divisibility
Optimal O(n²) O(n) Use prefix sums to compute substring sums in O(1) per substring

Algorithm Walkthrough

  1. Create a mapping from letters 'a' to 'z' to their corresponding keypad values according to the given scheme. This allows fast O(1) lookup for each character.
  2. Compute a prefix sum array prefix where prefix[i] contains the sum of mapped values from index 0 to i-1 in the string. This step allows the sum of any substring to be computed in O(1).
  3. Initialize a counter count to 0, which will track the number of divisible substrings.
  4. Iterate over all possible start indices i of substrings.
  5. For each start index, iterate over all possible end indices j (inclusive) for substrings starting at i.
  6. Compute the sum of the substring word[i:j] using the prefix sum array: substring_sum = prefix[j + 1] - prefix[i].
  7. Check if substring_sum % length_of_substring == 0. If yes, increment count.
  8. After checking all substrings, return the counter.

Why it works: By using prefix sums, we efficiently calculate the sum of any substring and directly check the divisibility condition. The algorithm examines all possible substrings systematically, ensuring completeness.

Python Solution

class Solution:
    def countDivisibleSubstrings(self, word: str) -> int:
        # Mapping of letters to digits based on classic phone keypad
        keypad = {
            'a':1, 'b':2, 'c':3,
            'd':2, 'e':3, 'f':3,
            'g':4, 'h':5, 'i':4,
            'j':1, 'k':2, 'l':3,
            'm':4, 'n':5, 'o':6,
            'p':7, 'q':8, 'r':9, 's':7,
            't':8, 'u':9, 'v':8,
            'w':9, 'x':9, 'y':9, 'z':9
        }
        
        n = len(word)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + keypad[word[i]]
        
        count = 0
        for i in range(n):
            for j in range(i, n):
                substring_sum = prefix[j + 1] - prefix[i]
                length = j - i + 1
                if substring_sum % length == 0:
                    count += 1
        return count

The implementation first creates a fast lookup mapping for characters to digits. The prefix sum array allows constant-time substring sum computation. Nested loops enumerate all possible substrings, and the divisibility check increments the counter efficiently.

Go Solution

func countDivisibleSubstrings(word string) int {
    keypad := map[rune]int{
        'a':1, 'b':2, 'c':3,
        'd':2, 'e':3, 'f':3,
        'g':4, 'h':5, 'i':4,
        'j':1, 'k':2, 'l':3,
        'm':4, 'n':5, 'o':6,
        'p':7, 'q':8, 'r':9, 's':7,
        't':8, 'u':9, 'v':8,
        'w':9, 'x':9, 'y':9, 'z':9,
    }
    
    n := len(word)
    prefix := make([]int, n+1)
    for i, ch := range word {
        prefix[i+1] = prefix[i] + keypad[ch]
    }
    
    count := 0
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            sum := prefix[j+1] - prefix[i]
            length := j - i + 1
            if sum % length == 0 {
                count++
            }
        }
    }
    return count
}

The Go version mirrors the Python implementation. We use rune in the map to handle characters properly, slices for the prefix array, and integer arithmetic for the divisibility check. count accumulates the result, which is returned at the end.

Worked Examples

Example 1: word = "asdf"

Mapping: a=1, s=7, d=2, f=3

Prefix sums: [0,1,8,10,13]

Substring Sum Length Divisible?
a 1 1 Yes
s 7 1 Yes
d 2 1 Yes
f 3 1 Yes
as 8 2 Yes
sd 9 2 No
df 5 2 No
asd 10 3 No
sdf 12 3 Yes
asdf 13 4 No

Count = 6

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Two nested loops over string length n; prefix sum computation is O(n)
Space O(n) Prefix sum array stores n+1 integers

The prefix sum array reduces repeated sum computation, making the nested loops efficient enough for n ≤ 2000.

Test Cases

# Basic examples
assert Solution().countDivisibleSubstrings("asdf") == 6  # Example 1
assert Solution().countDivisibleSubstrings("bdh") == 4   # Example 2
assert Solution().countDivisibleSubstrings("abcd") == 6  # Example 3

# Single character
assert Solution().countDivisibleSubstrings("a") == 1

# All same characters
assert Solution().countDivisibleSubstrings("aaa") == 6

# No divisible substring beyond single characters
assert Solution().countDivisibleSubstrings("gz") == 2

# Maximum length test
assert Solution().countDivisibleSubstrings("a"*2000) == 2001000  # sum of first 2000 numbers
Test Why
"asdf" Validates example from problem
"bdh" Validates example from problem
"abcd" Validates example from problem
"a" Single character substring
"aaa" All characters same
"gz" No divisible substring beyond length 1
"a"*2000 Stress test for large input

Edge Cases

Single character string: This ensures that the function correctly handles minimal input. Any single character is always divisible by its length, which is 1. The prefix sum array and nested loop handle this automatically.

All characters identical: For a string like "aaa", multiple substrings can have the same sum divisible by their