How hard is LeetCode 2950. Number of Divisible Substrings?

LeetCode 2950. Number of Divisible Substrings is rated Medium on LeetCode.

What is the time complexity of LeetCode 2950. Number of Divisible Substrings?

The Python solution on this page runs in O(n^2).

What is the space complexity of LeetCode 2950. Number of Divisible Substrings?

The Python solution on this page uses O(C) auxiliary space.

What topics does LeetCode 2950. Number of Divisible Substrings cover?

LeetCode 2950. Number of Divisible Substrings is tagged Hash Table, String, Counting and Prefix Sum on LeetCode.

Is LeetCode 2950. Number of Divisible Substrings a premium problem?

Yes. LeetCode 2950. Number of Divisible Substrings is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Number of Divisible Substrings — LeetCode 2950 Python Solution

MediumLeetCode PremiumHash TableStringCountingPrefix Sum

Problem: #2950
Pattern: Prefix Sum
Reading time: 3 min
Source: leetcode.com

The problem

Each character of the English alphabet has been mapped to a digit as shown below. A string is divisible if the sum of the mapped values of its characters is divisible by its length.

Example

Input: word = "asdf"
Output: 6
Explanation: The table above contains the details about every substring of word, and we can see that 6 of them are divisible.

Python solution

Python

class Solution:
    def countDivisibleSubstrings(self, word: str) -> int:
        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
        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

Complexity

Measure	Complexity
Time	O(n^2)
Space	O(C) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2950. Number of Divisible Substrings is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2950. Number of Divisible Substrings?: LeetCode 2950. Number of Divisible Substrings is rated Medium on LeetCode.
What is the time complexity of LeetCode 2950. Number of Divisible Substrings?: The Python solution on this page runs in O(n^2).
What is the space complexity of LeetCode 2950. Number of Divisible Substrings?: The Python solution on this page uses O(C) auxiliary space.
What topics does LeetCode 2950. Number of Divisible Substrings cover?: LeetCode 2950. Number of Divisible Substrings is tagged Hash Table, String, Counting and Prefix Sum on LeetCode.
Is LeetCode 2950. Number of Divisible Substrings a premium problem?: Yes. LeetCode 2950. Number of Divisible Substrings is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.