1876. Substrings of Size Three with Distinct Characters

EasyHash TableStringCountingSliding Window

Problem Description

The problem presents a scenario where we have to find substrings of length three without any repeating characters, defined as good substrings, within a given string s. It's important to remember that substrings are consecutive characters found within s.

An important detail is that each occurrence of such a good substring counts separately even if they are the same combinations of characters. So if "abc" occurs five times in different parts of string s, it counts as five good substrings.

The goal is to return the total number of such good substrings found in s.

Intuition

Coming up with the intuition for solving this problem involves realizing that we can check every substring of length three within the string s sequentially.

For each position in the string, starting from the first character and moving towards the last possible position for a substring of length three, we can check whether the three consecutive characters at that position are all different. If they are indeed all unique, then we have identified a good substring.

The approach is to loop through the string starting from the first character and ending two characters before the last one (since we're looking at substrings of length three), and for each position, check the uniqueness of the characters. We increment a count whenever we identify a unique combination, which indicates a good substring.

Since we only need to verify the distinctness of three characters at a time, the checks can be done quickly and efficiently, leading to a solution with linear time complexity, as the number of checks is directly proportional to the length of the string s.

Learn more about Sliding Window patterns.

Solution Approach

The solution for this problem is implemented using a single for-loop that iterates from index 0 to n - 2 of the input string s, where n is the length of the string. This is done to make sure that we can always check substrings of exactly three characters until the end of the string without going out of range.

Inside the loop, for each index i, the characters at position i, i + 1, and i + 2 are compared to each other. The logic of the comparison is that a substring is good if and only if no two characters out of the three are equal. This is directly translated into the code by the conditional expression:

s[i] != s[i + 1] and s[i] != s[i + 2] and s[i + 1] != s[i + 2]

If the above expression evaluates to True, it means that all three characters are unique, and thus, we found a good substring. The code uses this truthy or falsey value to increment the count. Since True is equivalent to 1 and False is equivalent to 0 in Python, the expression directly contributes to the count.

No additional data structures are used or needed since the task is simply to count instances, and therefore, memory usage is minimal.

The simplicity of this approach is in its linear time complexity (O(n)), as it only requires a single pass through the string, checking each set of three characters exactly once. This makes it optimal for strings of any length.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's apply the solution approach to a small example to understand how it works. Suppose we have the following string s:

s = "xyzzabc"

The goal is to find good substrings of length three within s without any repeating characters.

Now, following the solution approach, we will check each substring of length three:

Start with the first substring "xyz". This substring has no repeating characters, making it a good substring. So here, we increment our count to 1.
Move to the next substring "yzz". This contains repeating characters ('z'), so it is not a good substring. The count remains 1.
Next, we look at the substring "zza". This also has repeating characters ('z'), so it's not a good substring. The count is still 1.
Now, check "zab". All characters are unique here, so this is a good substring. Increase the count to 2.
Finally, we look at "abc", which also contains all unique characters. This is another good substring, so we increment the count to 3.

After iterating through the string s, we found a total of 3 good substrings. Hence, the outcome returned by the solution would be 3. The check for uniqueness is efficient as we compare only three characters at a time and increment the count based on the condition of uniqueness, leading to a solution with a linear runtime.

Solution Implementation

1class Solution:
2    def countGoodSubstrings(self, s: str) -> int:
3        # Initialize the count of good substrings
4        good_substring_count = 0
5      
6        # Calculate the length of the string for boundaries in the loop
7        string_length = len(s)
8      
9        # Loop through the string, stopping at the third-to-last character
10        for index in range(string_length - 2):
11            # Check if the current character, the next one, and the one after that are all unique
12            if s[index] != s[index + 1] and s[index] != s[index + 2] and s[index + 1] != s[index + 2]:
13                # If they are unique, we have found a good substring, so increment the count
14                good_substring_count += 1
15      
16        # After the loop, return the total count of good substrings found
17        return good_substring_count
18

1class Solution {
2
3    /**
4     * This method counts the number of good substrings in a given string.
5     * A good substring is defined as a substring with exactly 3 characters and each character is unique.
6     * 
7     * @param s The input string to be searched for good substrings.
8     * @return The number of good substrings found.
9     */
10    public int countGoodSubstrings(String s) {
11        int count = 0; // Initialize a counter to store number of good substrings
12        int n = s.length(); // Get the length of the input string
13
14        // Loop through the string, up to the third last character
15        for (int i = 0; i < n - 2; ++i) {
16            // Extract the current, next and the character after next characters
17            char firstChar = s.charAt(i);
18            char secondChar = s.charAt(i + 1);
19            char thirdChar = s.charAt(i + 2);
20
21            // Check if all three characters are distinct
22            if (firstChar != secondChar && firstChar != thirdChar && secondChar != thirdChar) {
23                // Increment the count if the substring is good
24                ++count;
25            }
26        }
27
28        // Return the total count of good substrings found
29        return count;
30    }
31}
32

1#include <string>
2
3// Function to count the number of good substrings in a given string.
4// A good substring is defined as a substring of length 3 with all unique characters.
5int countGoodSubstrings(const std::string& s) {
6    // Get the length of the string.
7    int length = s.length();
8    // Initialize the count of good substrings to zero.
9    int goodSubstringCount = 0;
10
11    // Iterate over each character in the string, stopping 2 characters before the end.
12    for (int i = 0; i < length - 2; ++i) {
13        // Extract the current character and the next two characters.
14        char char1 = s[i],
15             char2 = s[i + 1],
16             char3 = s[i + 2];
17
18        // Check if all three characters are distinct.
19        if (char1 != char2 && char1 != char3 && char2 != char3) {
20            // If they are, increment the count of good substrings.
21            ++goodSubstringCount;
22        }
23    }
24
25    // Return the total count of good substrings found in the string.
26    return goodSubstringCount;
27}
28

1// Function to count the number of good substrings in a given string.
2// A good substring is defined as a substring of length 3 with all unique characters.
3function countGoodSubstrings(s: string): number {
4    // Get the length of the string.
5    const length: number = s.length;
6    // Initialize the count of good substrings to zero.
7    let goodSubstringCount: number = 0;
8
9    // Iterate over each character in the string, stopping 2 characters before the end.
10    for (let i: number = 0; i < length - 2; ++i) {
11        // Extract the current character and the next two characters.
12        let char1: string = s.charAt(i),
13            char2: string = s.charAt(i + 1),
14            char3: string = s.charAt(i + 2);
15
16        // Check if all three characters are distinct.
17        if (char1 !== char2 && char1 !== char3 && char2 !== char3) {
18            // If they are, increment the count of good substrings.
19            ++goodSubstringCount;
20        }
21    }
22
23    // Return the total count of good substrings found in the string.
24    return goodSubstringCount;
25}
26

Time and Space Complexity

The given Python code snippet defines a method countGoodSubstrings which counts the number of substrings of length 3 with all unique characters within a given string s.

Time Complexity

To analyze the time complexity, we look at the number of operations that the code performs. The for loop runs from 0 to n - 2, where n is the length of the string s. Within each iteration of the loop, there are constant time comparisons being made: checking whether s[i], s[i + 1], and s[i + 2] are all unique characters. Since the number of iterations is dependent on the length of the input string, and all operations within the loop are constant time, the time complexity is O(n), where n is the length of the input string s.

Space Complexity

Considering the space complexity, the code utilizes a fixed amount of extra space: a single integer count to keep track of the number of good substrings, and an integer n for storing the length of the string. No additional space that grows with the input size is used. Thus, the space complexity is constant, or O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don’t know