Leetcode 1876: Substrings of Size Three with Distinct Characters
You are given a string
s, and your task is to find the number of substrings of length 3 that contain no repeated characters. A substring is considered ‘good’ if all its characters are unique. Note that if a ‘good’ substring appears more than once, it should be counted multiple times.Problem
Approach
Steps
Complexity
Input: You are given a string `s` which consists of lowercase English letters.
Example: For s = "abcabc".
Constraints:
• 1 <= s.length <= 100
• s consists of lowercase English letters.
Output: Return the number of 'good' substrings of length 3 in the string `s`.
Example: For the input s = "abcabc", the output is 4.
Constraints:
• The output should be a non-negative integer.
Goal: We need to find all substrings of length 3 and count those that have no repeated characters.
Steps:
• Iterate through the string from index 0 to n - 3.
• For each position, extract the substring of length 3 and check if all characters are unique.
• Count the valid substrings where all characters are distinct.
Goal: The string `s` should be a non-empty string containing only lowercase English letters.
Steps:
• 1 <= s.length <= 100
• s consists of lowercase English letters.
Assumptions:
• The string `s` contains at least one substring of length 3.
• Input: For the input s = "abcabc".
• Explanation: The substrings of length 3 are: 'abc', 'bca', 'cab', and 'abc'. All of these are 'good' substrings since they contain unique characters.
• Input: For the input s = "aababcabc".
• Explanation: The substrings of length 3 are: 'aab', 'aba', 'bab', 'abc', 'bca', 'cab', 'abc'. The 'good' substrings are 'abc', 'bca', and 'cab'.
Approach: To solve this problem, we can iterate over the string and extract all substrings of length 3. Then, we check whether all the characters in the substring are unique.
Observations:
• We need to consider substrings of fixed length 3.
• We can efficiently check for uniqueness using a set.
• Checking each substring for uniqueness will take O(1) time using a set, and iterating through the string will take O(n).
Steps:
• Loop through the string from index 0 to n - 3.
• Extract each substring of length 3 and check if all characters are distinct using a set.
• Increment the count for every valid substring.
Empty Inputs:
• Not applicable as the string length is at least 1.
Large Inputs:
• The algorithm should handle strings of length up to 100.
Special Values:
• Test strings with repeated characters only, such as 'aaa'.
Constraints:
• Ensure that only substrings of exactly length 3 are considered.
int countGoodSubstrings(string s) {
int cnt = 0;
for(int i = 2; i < s.size(); i++)
if(s[i] != s[i - 1] && s[i - 1] != s[i - 2] && s[i - 2] != s[i]) cnt++;
return cnt;
}
1 : Initialization
int countGoodSubstrings(string s) {
Define a function to count substrings of size 3 with unique characters.
2 : Initialization
int cnt = 0;
Initialize a counter to track the number of valid substrings.
3 : Loop
for(int i = 2; i < s.size(); i++)
Iterate through the string starting from the third character.
4 : Condition
if(s[i] != s[i - 1] && s[i - 1] != s[i - 2] && s[i - 2] != s[i]) cnt++;
Check if the current substring of size 3 has distinct characters; if yes, increment the counter.
5 : Return
return cnt;
Return the total count of valid substrings after processing the string.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We iterate through the string once and check each substring of length 3, which takes O(n) time.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we only use a set to check the uniqueness of characters in each substring.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus