Teaching Kids Programming – Anagram Substrings via Sliding Window

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two strings s0 and s1, return the number of substrings where s1 contains any anagram of s0.

Constraints
n ≤ 100,000 where n is the length of s0
m ≤ 100,000 where m is the length of s1
Example 1
Input
s0 = “abc”
s1 = “bcabxabc”
Output
3
Explanation
The substrings “bca”, “cab” and “abc” of s0 are permutations of “abc”.

Hints:
Sliding window, what could change between each successive window?

Anagram Substrings via Sliding Window Algorithm

We are looking for a fixed-size substring in s1 so that we can use a sliding window and update the Counter. When we shift the sliding window by one, the left-most character is removed from the window, and the next character is added.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def countAnagramSubstrings(self, s0, s1):
        ans = 0
        R = n0 = len(s0)
        n1 = len(s1)
        c = Counter(s0)
        cur = Counter(s1[:n0])
        if c == cur:
            ans += 1
        while R < n1:
            cur[s1[R]] += 1
            cur[s1[R - n0]] -= 1
            if cur[s1[R - n0]] == 0:
                del cur[s1[R - n0]]
            if cur == c:
                ans += 1
            R += 1            
        return ans

class Solution:
    def countAnagramSubstrings(self, s0, s1):
        ans = 0
        R = n0 = len(s0)
        n1 = len(s1)
        c = Counter(s0)
        cur = Counter(s1[:n0])
        if c == cur:
            ans += 1
        while R < n1:
            cur[s1[R]] += 1
            cur[s1[R - n0]] -= 1
            if cur[s1[R - n0]] == 0:
                del cur[s1[R - n0]]
            if cur == c:
                ans += 1
            R += 1            
        return ans

The time complexity is O(NM) where N is the length of s1 and M is the length of s0. The space complexity is O(M) for keeping the sliding window.

–EOF (The Ultimate Computing & Technology Blog) —