Day 24 ; Nice substring with sliding window Pattern

Hello and welcome back brave human being,

Before we get into today’s problem, I want to share what I realized this week.

Relaxation is the key to mastery.

I used to think the more stressed I am the more I can produce but tension and anger may produce a positive experience occasionally, but I promise it was not the best result possible.

The best results are produced when you are relaxed!!!

Now, this is easier said than done but just try to breathe once, and then breathe out……

It’s easy to find examples from your own life:

When you tension yourself to deliver a creative task, you become less creative.

When you push yourself to find friends, you rarely attract the right crowd.

When you force yourself to think of a solution to a LeetCode problem, the solution rarely comes to you..

So just try to breath once maybe twice before continuing reading!

Day 24: 1876. Substrings of Size Three with Distinct Characters

Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​.

A string is good if there are no repeated characters.

if your first instinct when reading this problem is to use a double-for-loop to calculate all possible substrings, you are on the right path, but this is an expensive path 💸. This approach would have an O(n2) time complexity.

Let’s dive in 🤿 :

To determine if a substring is "nice," it must contain only unique characters. The ideal data structure for this task is a frequency map, where the key is the character and the value is its frequency. If the frequency of any character is more than one, the substring is not nice.

Now that we’ve identified how to check if a substring is nice. How would we formulate the substrings?

We’ve determined that calculating all of them is quite expensive but we can leverage what we learned last week, a sliding window (fresher on the pattern) .

Our window will be represented by our frequency map. As we slideeeeeee through the string, we can remove the first element from our window and add a new character to it. This way, we maintain an updated frequency map for the current window of characters, allowing us to quickly check if the substring is “nice” or not.

Let’s set out an example:

Complete Solution:

class Solution {
public:
    int countGoodSubstrings(string s) {
        if (s.size() < 3) {
            return 0;
        }

        map<char, int> freq;
        int count = 0;

        // Initialize the frequency map with the first two characters
        for (int i = 0; i < 2; ++i) {
            freq[s[i]]++;
        }

        for (int i = 2; i < s.size(); ++i) {
            // Add the third character to the current window
            freq[s[i]]++;

            // Check if the current window has all unique characters
            if (freq.size() == 3) {
                count++;
            }

            // Remove the character that is sliding out of the window
            freq[s[i - 2]]--;
            if (freq[s[i - 2]] == 0) {
                freq.erase(s[i - 2]);
            }
        }

        return count;
    }
};

Using the sliding window would allow us to reduce the Time complexity to O(N) and only use a space complexity of O(1), as the map in any given time only has 3 characters.

See youuuuuuuuuu Friday for the next problem.