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.
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".
Constraints:
1 <= s.length <= 100
s
consists of lowercase English letters.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force strategy for this problem is quite simple. We will look at every single possible group of three characters in the given string and check if that group meets the requirements.
Here's how the algorithm would work step-by-step:
def count_good_substrings(input_string):
string_length = len(input_string)
good_substring_count = 0
# Iterate through the string, checking substrings of length 3
for index in range(string_length - 2):
substring = input_string[index:index + 3]
# Check if the substring has distinct characters
if (substring[0] != substring[1] and \
substring[0] != substring[2] and \
substring[1] != substring[2]):
good_substring_count += 1
return good_substring_count
Instead of checking every possible three-letter chunk, we can slide a window of size three across the input. We only need to check each window to see if it contains unique characters; if it does, we count it.
Here's how the algorithm would work step-by-step:
def count_good_substrings(word):
substring_count = 0
string_length = len(word)
# Iterate through the string using a sliding window of size 3
for i in range(string_length - 2):
substring = word[i:i+3]
# Check if the characters in the substring are distinct
if len(set(substring)) == 3:
# Distinct characters found
substring_count += 1
return substring_count
Case | How to Handle |
---|---|
Null or empty input string | Return 0 immediately as there are no substrings to evaluate. |
Input string with length less than 3 | Return 0 as a substring of length 3 cannot be formed. |
Input string with all identical characters (e.g., 'AAA') | The sliding window will never contain distinct characters; the count will remain 0. |
Input string with all distinct characters (e.g., 'ABCDEF') | Every substring of length 3 will be distinct; the count will equal len(s)-2. |
Input string with a mix of distinct and duplicate characters (e.g., 'AABCA') | The sliding window correctly identifies and counts only the distinct substrings. |
Long input string (scalability considerations) | The sliding window approach provides O(n) time complexity, scaling linearly with input size. |
Input string with unicode characters | The solution should handle unicode characters correctly as long as the comparison and character counting mechanism supports them. |
String containing only non-alphanumeric characters | The character uniqueness check should work the same regardless of whether the characters are alphanumeric or special characters. |