Substrings of Size Three with Distinct Characters
Problem Description
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.
What is a substring?
A substring is a contiguous sequence of characters within a string. For a string s = "abcdef", a substring must consist of characters that appear consecutively in the original string.
Single-character substrings:
"a", "b", "c", "d", "e", "f"
Two-character substrings:
"ab", "bc", "cd", "de", "ef"
Three-character substrings:
"abc", "bcd", "cde", "def"
Four-character substrings:
"abcd", "bcde", "cdef"
Five-character substrings:
"abcde", "bcdef"
Six-character substring (the whole string itself):
"abcdef"
Invalid Substrings (Non-contiguous sequences):
"acd", "ace", "bac", etc., are not substrings because they skip over characters or mix up the order of characters in s.
Example of Substrings of Size Three with Distinct Characters
Example
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 which has all unique characters in it is "xyz". While “zaz” or “pizza” or “yzz” are not good substrings since it has at least one repeating character.
Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc". The good substrings which have all unique characters in them are "abc", "bca", "cab", and "abc".
While "aab", "aba" or "bab" are not good susbtrings since it has atleast one repeating character.
Constraints:
- 1 <= s.length <= 100
- s consists of lowercase English letters.
This problem is straightforward since we have to simply check whether the three consecutive characters are different or not.
Optimized Approach
Intuition
Since we are given a string-based question and we are asked to calculate the number of substrings of size 3 with unique characters, the first thing that comes to our mind is that we can check whether there are three consecutive characters where none of them are equal to each other.
If none of the three are equal to one another, we can increment our counter.
What we will be doing is, we will iterate the whole string till string.length-3(inclusive) and we will just perform our checks until the next two characters.
In the end, we will have our solution.
Why string.length() - 3 ?
If we go beyond string.length() - 3, we won't be able to extract the next two characters and if we are accessing the next two characters that are not present, it results in an "Index out of Bound "error.
Approach
Initialize count = 0:
- We initialize a variable count to 0. This variable will keep track of how many "good" substrings we find as we process the string.
Loop through the string:
- The loop starts at index i = 0 and iterates until i = length of s - 3. This ensures that we always have enough characters left in the string for comparison.
- The condition i <= length of s - 3 is used because for a substring of size 3, the last possible starting point is at s[length of s - 3] (to access characters s[i], s[i+1], and s[i+2]).
Check distinct characters:
- For each valid starting index i, we check the characters at s[i], s[i+1], and s[i+2] (the substring of length 3 starting at i). If all three characters are distinct, it means we have found a "good" substring.
Increment count:
- If the condition for distinct characters is true, we increment the count by 1.
Return count:
- Once we finish iterating through all possible substrings, the function returns the total number of "good" substrings found.
Dry-Run
Example
s= "abccdbaadc"
Output: 4
Explanation: “abc”, “cdb”, “adc” are the three substrings of str of size 3 with unique characters and “bcc” or “baa” are not as they have at least one repeating character.
Steps:
- Start with count = 0.
- Check each substring of length 3:
- If all characters in the substring are different, add 1 to count.
Substrings:
- "abc": All characters are different → Count = 1.
- "bcc": Characters are not all different → Count = 1.
- "ccd": Characters are not all different → Count = 1.
- "cdb": All characters are different → Count = 2.
- "dba": All characters are different → Count = 3.
- "baa": Characters are not all different → Count = 3.
- "aad": Characters are not all different → Count = 3.
- "adc": All characters are different → Count = 4.
Final Count:
The total number of "good" substrings is 4.
Optimal Codes in all Languages
1. C++ Try on Compiler
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
int countGoodSubstrings(string s) {
int count = 0;
// Iterate through all substrings of length 3
for (int i = 0; i <= s.length() - 3; i++) {
// Check if all characters in the substring are distinct
if (s[i] != s[i + 1] && s[i + 1] != s[i + 2] && s[i] != s[i + 2]) {
count++;
}
}
return count;
}
};
2. Java Try on Compiler
import java.util.Scanner;
public class Solution {
public int countGoodSubstrings(String s) {
int count = 0;
// Iterate through all substrings of length 3
for (int i = 0; i <= s.length() - 3; i++) {
// Check if all characters in the substring are distinct
if (s.charAt(i) != s.charAt(i + 1) &&
s.charAt(i + 1) != s.charAt(i + 2) &&
s.charAt(i) != s.charAt(i + 2)) {
count++;
}
}
return count;
}
}
3. Python Try on Compiler
class Solution:
def countGoodSubstrings(self, s: str) -> int:
count = 0
# Iterate through all substrings of length 3
for i in range(len(s) - 2):
# Check if all characters in the substring are distinct
if s[i] != s[i + 1] and s[i + 1] != s[i + 2] and s[i] != s[i + 2]:
count += 1
return count
4. JavaScript Try on Compiler
const countGoodSubstrings = (s) => {
let count = 0;
// Iterate through all substrings of length 3
for (let i = 0; i <= s.length - 3; i++) {
// Check if all characters in the substring are distinct
if (s[i] !== s[i + 1] && s[i + 1] !== s[i + 2] && s[i] !== s[i + 2]) {
count++;
}
}
return count;
};
Time Complexity = O(n)
Loop Iteration: The for-loop runs from index 0 to s.length() - 3 . This gives us n - 3 iterations where n is the length of the string s. Thus, the time complexity of the loop is O(n).
Character Comparison: The comparison of three characters (character at 0th, 1st and 2nd indices) also takes constant time O(1).
Since all operations inside the loop are constant time operations, the “overall time complexity is O(n)”, where n is the length of the string.
Space Complexity = O(n)
Auxiliary Space Complexity:-
Auxiliary space refers to the extra space used by the algorithm that is not part of the input.
The code only uses a constant amount of extra space for the count variable the auxiliary space complexity is O(1).
Total Space Complexity:-The total space includes both the auxiliary space and the space required for the input string s of length n.
The input string itself requires O(n) space.Therefore, the total space complexity is O(n).
The solution that we figured out involved fixed-size substrings, like finding substrings of length three without repeating characters. The approach is often straightforward as the size is less.
What if the window size (the length of the substring you're examining) is close to the size of the string n, you might end up with a performance issue, leading to a time complexity of O(n²). This happens because you could be checking each possible substring, which can result in redundant work.
To avoid this inefficiency, we can introduce the concept of a sliding window. The idea is to maintain a "window" of fixed size (in this case, size n) and "slide" it across the string, one character at a time. As the window moves, you can update the substring quickly by removing the effect of the character that leaves the window and adding the new character that enters.
This reduces the number of checks needed for each new substring, making the solution run more efficiently—closer to O(n) instead of O(n²).
Essentially, a sliding window allows you to reuse information from the previous substring, which helps avoid re-computation and improves performance.
For the "good substrings" problem, the sliding window will help check each substring of length 3 and determine if it has all unique characters in O(1) time per window shift, ensuring your solution is efficient.
You simply iterate through the string, focusing on groups of the given size, as the size remains constant.
Once we move further into sliding window algorithms, we will encounter problems where we have to maintain a window of dynamic size for the optimization.
We must explore Maps a bit more where we can learn about the functionalities it offers.
Try to understand Hash-Table by self-dry running using pen and paper.
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
- Minimum Size Subarray Sum
- Count the Number of Substrings With Dominant Ones
- Longest Substring Without Repeating Characters
- Maximum Number of Occurrences of a Substring
You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:
- The length of the subarray is k, and
- All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.
A subarray is a contiguous non-empty sequence of elements within an array.