1876. Substrings of Size Three with Distinct Characters
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.
What's the relationship between a tree and a graph?
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:
1s[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.
What data structure does Breadth-first search typically uses to store intermediate states?
Example Walkthrough
Let's apply the solution approach to a small example to understand how it works. Suppose we have the following string s:
1s = "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 to1. -
Move to the next substring
"yzz". This contains repeating characters ('z'), so it is not a good substring. The count remains1. -
Next, we look at the substring
"zza". This also has repeating characters ('z'), so it's not a good substring. The count is still1. -
Now, check
"zab". All characters are unique here, so this is a good substring. Increase the count to2. -
Finally, we look at
"abc", which also contains all unique characters. This is another good substring, so we increment the count to3.
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
181class 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}
321#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}
281// 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}
26Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
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.
Which two pointer technique does Quick Sort use?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.