MediumNo. 2950LeetCode Premium
Number of Divisible Substrings — LeetCode 2950 Python Solution
- Pattern
- Prefix Sum
- Topics
- Hash Table, String, Counting, 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
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 ansComplexity
- Time
- O(n2)
- Space · auxiliary
- O(C)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1737 | Change Minimum Characters to Satisfy One of Three Conditions | Medium |
| 2947 | Count Beautiful Substrings I | Medium |
| 0299 | Bulls and Cows | Medium |
| 0383 | Ransom Note | Easy |
| 0387 | First Unique Character in a String | Easy |
| 0451 | Sort Characters By Frequency | Medium |
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(n2).
- 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.