To solve this problem, we need to count the number of substrings of string s that are anagrams of any substring of string t. An anagram of a substring must have the same length as the substring, so we can leverage this property to efficiently check for valid substrings using sliding window frequency counts.
Approach
-
Precompute Frequency Counts for Substrings of
t:- For each possible length
L(from 1 to the length oft), compute the frequency of characters for all substrings oftof lengthLusing a sliding window technique. Store these frequency counts in a dictionary where the key is the lengthLand the value is a set of tuples (since tuples are hashable) representing the frequency counts.
- For each possible length
-
Check Substrings of
s:- For each possible length
L(from 1 to the minimum of the lengths ofsandt), compute the frequency counts of substrings ofsof lengthLusing the sliding window technique. Check if each frequency count exists in the precomputed set for lengthLfromt. If it does, increment the result count.
- For each possible length
Solution Code
from collections import defaultdict
def get_t_freqs(t):
t_freqs = defaultdict(set)
m = len(t)
for L in range(1, m + 1):
freq = [0] * 26
# Initial window for length L
for i in range(L):
c = t[i]
freq[ord(c) - ord('a')] += 1
t_freqs[L].add(tuple(freq))
# Slide the window across t
for i in range(L, m):
left_c = t[i - L]
freq[ord(left_c) - ord('a')] -= 1
curr_c = t[i]
freq[ord(curr_c) - ord('a')] += 1
t_freqs[L].add(tuple(freq))
return t_freqs
def count_anagram_substrings(s, t):
if not s or not t:
return 0
t_freqs = get_t_freqs(t)
n = len(s)
m = len(t)
max_L = min(n, m)
result = 0
for L in range(1, max_L + 1):
if L not in t_freqs:
continue
target_set = t_freqs[L]
freq = [0] * 26
# Initial window for s of length L
for i in range(L):
c = s[i]
freq[ord(c) - ord('a')] += 1
if tuple(freq) in target_set:
result += 1
# Slide the window across s
for i in range(L, n):
left_c = s[i - L]
freq[ord(left_c) - ord('a')] -= 1
curr_c = s[i]
freq[ord(curr_c) - ord('a')] += 1
if tuple(freq) in target_set:
result += 1
return result
Explanation
-
Precompute Frequency Counts: For each length
Lint, we use a sliding window to compute the frequency of characters for all substrings of lengthL. This helps in quickly checking if a substring ofsof the same length is an anagram of any substring oft. -
Check Substrings: For each length
Lins(up to the length oft), we compute the frequency of characters for each substring ofsof lengthLand check if it exists in the precomputed set of frequencies fortof lengthL. This ensures we only count valid anagram substrings.
This approach efficiently handles the problem by leveraging sliding window techniques and frequency counts, making it feasible for moderate-sized strings. The time complexity is O(m² + n*m) where m is the length of t and n is the length of s, which is manageable for most practical cases.
Example:
- Input:
s = "ab", t = "ba" - Output:
3(substrings "a", "b", "ab" are valid anagrams of substrings in "ba").
This solution correctly counts all valid substrings and handles edge cases like empty strings or strings of different lengths. It is optimal and easy to understand.


作者声明:本文包含人工智能生成内容。