3573. Count Substrings That Can Be Rearranged to Contain a String I
My accepted Python solution to LeetCode problem 3573, Count Substrings That Can Be Rearranged to Contain a String I, running in 291ms.
- Difficulty: Medium
- Python
- Runtime 291ms
- Memory 18.1MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 291ms, memory 18.1MB, accepted 2026-01-02.
class Solution:
def validSubstringCount(self, word1: str, word2: str) -> int:
from collections import Counter
need = Counter(word2)
window = Counter()
result = 0
left = 0
formed = 0
required = len(need)
for right, c in enumerate(word1):
window[c] += 1
if c in need and window[c] == need[c]:
formed += 1
while formed == required:
result += len(word1) - right
window[word1[left]] -= 1
if word1[left] in need and window[word1[left]] < need[word1[left]]:
formed -= 1
left += 1
return result