This week I’m studying the sliding window pattern.

According to Sergey Piterman, this type of coding pattern is commonly used in array or string coding problems, where you are looking at a moving sub-list of a string or array, which runs over an underlying string or array.

Piterman says the types of problems that you’d want to use the sliding window on typically involve the following:

• The problem uses a sorted or iterable data structure (like arrays, strings)

• The problem asks for a sequence, substring, sub-list, or subrange

• The problem asks for a shortest, longest, or target value

With that in mind, I wanted to study a easy sliding window problem to get an introduction to the way it is used, so I headed over to https://leetcode.com/tag/sliding-window/, and sorted the problems by difficulty. Then I decided to open https://leetcode.com/problems/substrings-of-size-three-with-distinct-characters/ because it had the highest acceptance rate among the easy questions.

This problem is called Substrings of Size Three with Distinct Characters. Here is the problem prompt from the leetcode website:

“A string is good if there are no repeated characters. Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​. Note that if there are multiple occurrences of the same substring, every occurrence should be counted. A substring is a contiguous sequence of characters in a string.”

Here are the examples from the problem description on the leetcode website:

Example 1:

Input: s = “xyzzaz”
Output: 1
Explanation: There are 4 substrings of size 3: “xyz”, “yzz”, “zza”, and “zaz”.
The only good substring of length 3 is “xyz”.
Example 2:

Input: s = “aababcabc”
Output: 4
Explanation: There are 7 substrings of size 3: “aab”, “aba”, “bab”, “abc”, “bca”, “cab”, and “abc”.
The good substrings are “abc”, “bca”, “cab”, and “abc”.

My initial thoughts on this problem are, we’re looking at strings, and specifically, a substring, which makes sense for a sliding window problem. I think it is important to note that the problem prompt includes the statement ‘no repeated characters’. The other noteworthy part of the prompt statement is it gives us a substring length of three, so we know our window size is three characters.

Another way to look at this problem is, we’re iterating over a string in lengths of three characters at a time, and we’re looking for the number of occurrences of when those three characters are unique.

We need to start at the beginning of the string, and setup our sliding window, looking at three characters at a time. We need a condition which checks for a ‘good’ substring, and when we find it, we need a structure of some kind of keep track of that number of occurrences. After we’ve looked at the three characters in the current window, we need to move the window a step forward, and look at the next three in the string. So we also need a structure to keep track of where we are in the string, so we know the locations of the beginning and end.

To iterate over the length of the string, we could use a for loop, with a range that has the beginning character and end character represented by the length of the string, and then access each element with indexing. What concerns me with this approach is going out of range. I think we need a condition which checks that the window size, plus the current position is less than the length of the string.

And how do we implement the actual sliding window itself? Well possibly, we could use variables to take on the different indexes or positions in the string. And then how do we check the characters inside the window, for uniqueness? It seems like we need pointers, for first, second, and third positions.

After thinking through the problem, step by step, I put together a potential solution.

I could use the positions of the string in the window, represented by first, second and third, and then use a while loop condition that makes sure I don’t go over the length of the string with the window size.

If I find that first, second, and third are unique, I want to increment my total count of good stings that I found, but if they aren’t unique, I could add zero. To optimize this further, it could probably be removed, but it helped my thought process. I need to move my window forward, so I need to increment where I’m pointing to with first, second and third each time I move forward. Regardless of whether I find a good string or not, I have to keep moving the window forward, so I increment my pointer locations each time.

class Solution(object):
    def countGoodSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """

        good_string_count = 0
        window_size = 3
        first = 0
        second = 1
        third = 2
        
        while first + window_size < len(s):
            if s[first] != s[second] != s[third]:
                good_string_count += 1
            else:
                good_string_count += 0
            first+=1
            second+=1
            third+=1
        return good_string_count

When I clicked ‘run’, the result was accepted, but before clicking submit, I’d like to go through a few test cases and try to find if it really works.

And it’s a good thing that I checked, because my code passed when the test case was “xyzzaz”, but it failed for the second example with the string “aababcabc”, so there must be something here that’s off with my thought process.

The main issue is in this line:

if s[first] != s[second] != s[third]:

I think the issue was corrected when I reconfigured my logic a little here:

if s[first] == s[second] or s[second] == s[third] or s[first] == s[third]:

My final solution looks like this:

class Solution(object):
    def countGoodSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """

        good_string_count = 0
        window_size = 3
        first = 0
        second = 1
        third = 2
        
        while first + window_size < len(s)+1:
            if s[first] == s[second] or s[second] == s[third] or s[first] == s[third]:
                good_string_count += 0
            else:
                good_string_count += 1
            first+=1
            second+=1
            third+=1
        return good_string_count

And the logic that I swapped or reversed was for adding to the good_string_count, to make sure that the conditions were correct to the window characters being the same. If the characters were compared with a double equal or comparison operator, then I don’t want to add that to my count of good strings. Instead, I could only account for the cases where these conditions are not true.

When I run my new solution with the two example test cases, it passed both of them.

When trying to come up with more potential edge cases, I checked the solution against these:

‘z’, ‘zzz’, ‘zz’, ‘zzza’

And then finally, when I thought I had exhausted all of the possibilities, I hit submit, and my solution was accepted. Yay.

Sources:

“How to Solve Sliding Window Problems – Outco.” Medium, 12 Feb. 2021, medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66.

“Substrings of Size Three with Distinct Characters.” LeetCode, leetcode.com/problems/substrings-of-size-three-with-distinct-characters. Accessed 23 Sept. 2022.