Problem Description

You are given a phone keypad mapping where each letter of the English alphabet is assigned a number from 1 to 9 based on old phone keypads:

• Number 1: maps to 'a', 'b'
• Number 2: maps to 'c', 'd', 'e'
• Number 3: maps to 'f', 'g', 'h'
• Number 4: maps to 'i', 'j', 'k'
• Number 5: maps to 'l', 'm', 'n'
• Number 6: maps to 'o', 'p', 'q'
• Number 7: maps to 'r', 's', 't'
• Number 8: maps to 'u', 'v', 'w'
• Number 9: maps to 'x', 'y', 'z'

A string is considered divisible if the sum of the mapped values of its characters is divisible by the string's length.

Given a string s, you need to find and return the total number of divisible substrings in s.

A substring is defined as a contiguous sequence of one or more characters within the string.

For example, if we have a substring "abc":

• 'a' maps to 1
• 'b' maps to 1
• 'c' maps to 2
• Sum = 1 + 1 + 2 = 4
• Length = 3
• Since 4 is not divisible by 3, this substring is not divisible

The task is to count all possible substrings of the given string where the sum of mapped values is divisible by the substring's length.

Intuition

The key insight is that we need to check every possible substring to determine if it's divisible. Since we need to examine all substrings anyway, a brute force approach makes sense here.

First, we need a way to quickly convert each character to its corresponding number. We can preprocess the mapping by creating a dictionary where each letter maps directly to its number value (1-9). This allows us to look up any character's value in constant time.

For checking divisibility, we need two pieces of information for each substring:

1. The sum of all mapped values in the substring
2. The length of the substring

The natural approach is to use nested loops - the outer loop fixes the starting position i of a substring, and the inner loop extends the ending position j. As we extend the substring from position i to j, we can maintain a running sum of the mapped values. This is efficient because instead of recalculating the entire sum for each substring, we just add the value of the new character at position j.

For a substring from index i to j, the length is j - i + 1. We check if the current sum is divisible by this length using the modulo operator: sum % (j - i + 1) == 0.

This approach ensures we examine all possible substrings exactly once, making it both complete and efficient given the constraints. Each substring is checked in O(1) time after the initial character mapping, resulting in an O(n²) overall complexity where n is the length of the input string.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation follows a straightforward enumeration strategy with preprocessing for the character-to-number mapping.

Step 1: Build the Character Mapping

First, we create a mapping dictionary mp to store which number each letter corresponds to:

• We define an array d where each string contains the letters mapped to positions 1-9
• We iterate through this array with enumeration starting from 1
• For each group of letters, we assign them their corresponding number value

d = ["ab", "cde", "fgh", "ijk", "lmn", "opq", "rst", "uvw", "xyz"]
mp = {}
for i, s in enumerate(d, 1):
    for c in s:
        mp[c] = i

This creates a dictionary where mp['a'] = 1, mp['b'] = 1, mp['c'] = 2, and so on.

Step 2: Enumerate All Substrings

We use nested loops to generate all possible substrings:

• The outer loop with index i represents the starting position of the substring
• The inner loop with index j represents the ending position of the substring
• For each starting position i, we examine all substrings that start at i and end at positions from i to n-1

Step 3: Calculate Sum and Check Divisibility

For each starting position i, we maintain a running sum s:

• When we extend the substring to include character at position j, we add mp[word[j]] to the sum
• The length of the current substring is j - i + 1
• We check if s % (j - i + 1) == 0 to determine if the substring is divisible
• If divisible, we increment our answer counter

ans = 0
n = len(word)
for i in range(n):
    s = 0
    for j in range(i, n):
        s += mp[word[j]]
        ans += s % (j - i + 1) == 0
return ans

The running sum optimization is crucial here - instead of recalculating the sum for each substring from scratch, we incrementally build it by adding one character's value at a time. This reduces the time complexity from O(n³) to O(n²).

The expression ans += s % (j - i + 1) == 0 is a concise way to increment the counter - it adds 1 when the condition is true (divisible) and 0 when false.

Example Walkthrough

Let's walk through the solution with the string s = "ace".

Step 1: Build the character mapping

• 'a' → 1 (from group "ab")
• 'c' → 2 (from group "cde")
• 'e' → 2 (from group "cde")

Step 2: Enumerate all substrings and check divisibility

Starting position i = 0 (character 'a'):

• j = 0: substring "a"

  • Sum = 1 (value of 'a')
  • Length = 0 - 0 + 1 = 1
  • Check: 1 % 1 = 0 ✓ (divisible)
  • Count = 1

• j = 1: substring "ac"

  • Sum = 1 + 2 = 3 (adding value of 'c')
  • Length = 1 - 0 + 1 = 2
  • Check: 3 % 2 = 1 ✗ (not divisible)
  • Count = 1

• j = 2: substring "ace"

  • Sum = 3 + 2 = 5 (adding value of 'e')
  • Length = 2 - 0 + 1 = 3
  • Check: 5 % 3 = 2 ✗ (not divisible)
  • Count = 1

Starting position i = 1 (character 'c'):

• j = 1: substring "c"

  • Sum = 2 (value of 'c')
  • Length = 1 - 1 + 1 = 1
  • Check: 2 % 1 = 0 ✓ (divisible)
  • Count = 2

• j = 2: substring "ce"

  • Sum = 2 + 2 = 4 (adding value of 'e')
  • Length = 2 - 1 + 1 = 2
  • Check: 4 % 2 = 0 ✓ (divisible)
  • Count = 3

Starting position i = 2 (character 'e'):

• j = 2: substring "e"
  • Sum = 2 (value of 'e')
  • Length = 2 - 2 + 1 = 1
  • Check: 2 % 1 = 0 ✓ (divisible)
  • Count = 4

Final Answer: 4 divisible substrings

The divisible substrings are: "a", "c", "ce", and "e".

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the string word. This is because we have two nested loops: the outer loop iterates through each starting position i from 0 to n-1, and the inner loop iterates from position i to n-1. The total number of iterations is n + (n-1) + (n-2) + ... + 1 = n(n+1)/2, which simplifies to O(n^2). All operations inside the inner loop (dictionary lookup, addition, modulo operation, and comparison) take O(1) time.

The space complexity is O(C), where C is the size of the character set. In this problem, C = 26 since we're dealing with lowercase English letters. The space is primarily used by the dictionary mp which stores a mapping from each character to its corresponding value. The dictionary has at most 26 entries (one for each lowercase letter). The list d and other variables use constant space, so the overall space complexity remains O(C) or O(26) which is effectively O(1) constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Division Confusion

Pitfall: Developers might mistakenly check for integer division instead of divisibility when determining if a substring qualifies.

Incorrect approach:

# Wrong: This checks if the division result is an integer (which it always is in Python 3)
if substring_sum / substring_length == int(substring_sum / substring_length):
    count += 1

Correct approach:

# Right: Use modulo operator to check divisibility
if substring_sum % substring_length == 0:
    count += 1

2. Recalculating Sum for Each Substring

Pitfall: Computing the sum from scratch for every substring leads to unnecessary redundant calculations and O(n³) time complexity.

Inefficient approach:

for start in range(n):
    for end in range(start, n):
        # Recalculating sum every time - inefficient!
        substring_sum = 0
        for k in range(start, end + 1):
            substring_sum += char_to_value[word[k]]
        if substring_sum % (end - start + 1) == 0:
            count += 1

Optimized approach:

for start in range(n):
    substring_sum = 0  # Initialize sum once per starting position
    for end in range(start, n):
        # Incrementally build the sum
        substring_sum += char_to_value[word[end]]
        if substring_sum % (end - start + 1) == 0:
            count += 1

3. Off-by-One Errors in Length Calculation

Pitfall: Incorrectly calculating the substring length, especially forgetting that array indices are 0-based.

Wrong calculation:

substring_length = end - start  # Missing the +1

Correct calculation:

substring_length = end - start + 1  # Proper length calculation

4. Hardcoding Character Mappings

Pitfall: Manually creating the character-to-value mapping with individual assignments, making the code verbose and error-prone.

Error-prone approach:

char_to_value = {
    'a': 1, 'b': 1,
    'c': 2, 'd': 2, 'e': 2,
    # ... 26 manual entries - easy to make typos
}

Better approach: Use the systematic pattern to generate the mapping programmatically, as shown in the solution.

5. Missing Edge Cases

Pitfall: Not considering single-character substrings or empty string inputs.

Solution: The nested loop structure naturally handles single-character substrings (when start == end), and empty strings will simply result in 0 since the outer loop won't execute. However, it's good practice to explicitly verify these cases work correctly.