We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Divisible Substrings

Number: 3237

Difficulty: Medium

Paid? Yes

Companies: Wayfair, IBM, Amdocs

Problem Description

Given a string s (consisting of lowercase English letters), every character is first mapped to a digit according to a fixed old phone digits mapping (for example, the sample shows that a maps to 1, s maps to 7, d maps to 2, and f maps to 3). A substring (a contiguous non-empty piece of s) is called divisible if the sum of the mapped values of its characters is divisible by the length of the substring. The task is to count how many substrings of s are divisible.

Key Insights

  • We can precompute a prefix sum array such that the sum of any substring from index i to j can be computed in O(1) time.
  • The divisibility test for a substring with sum S and length L is simply: S % L == 0.
  • Since s has at most 2000 characters, a double loop (O(n²)) to try every substring and test its divisibility is acceptable.

Space and Time Complexity

Time Complexity: O(n²) due to the nested loop over all substrings. Space Complexity: O(n) for storing the prefix sum array.

Solution

The solution works as follows:

  1. Set up a mapping from every lowercase letter to its corresponding digit as provided by the problem statement (for example, from the sample: a = 1, s = 7, d = 2, f = 3; the remaining mappings follow the same pattern).
  2. Build a prefix sum array where prefix[i+1] holds the sum of mapped digits for the substring s[0...i]. This lets us compute any substring’s sum as prefix[j+1] - prefix[i] in constant time.
  3. Use two nested loops to iterate over all substrings. For each substring, compute its sum and length, and check if the sum is divisible by the length.
  4. Count and return the number of substrings that satisfy the divisibility condition.

Code Solutions

# Python solution for counting divisible substrings

def countDivisibleSubstrings(word):
    # Mapping dictionary from letter to digit as per the provided old phone digits mapping.
    mapping = {
        'a': 1, 'b': 2, 'c': 3,
        'd': 2, 'e': 3, 'f': 3,
        'g': 4, 'h': 4, 'i': 4,
        'j': 5, 'k': 5, 'l': 5,
        'm': 6, 'n': 6, 'o': 6,
        'p': 7, 'q': 7, 'r': 7, 's': 7,
        't': 8, 'u': 8, 'v': 8,
        'w': 9, 'x': 9, 'y': 9, 'z': 9
    }
    
    n = len(word)
    # Create prefix sum array; prefix[i+1] = sum of mapped values up to index i.
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + mapping[word[i]]
    
    count = 0
    # Iterate over all substrings using two nested loops
    for i in range(n):
        for j in range(i, n):
            length = j - i + 1  # Length of the substring s[i...j]
            total = prefix[j+1] - prefix[i]  # Sum of the substring s[i...j]
            if total % length == 0:
                count += 1
    return count

# Example usage:
print(countDivisibleSubstrings("asdf"))  # Expected output: 6
← Back to All Questions