Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1876. Substrings of Size Three with Distinct Characters - Leetcode Solution

Code Implementation

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        count = 0
        for i in range(len(s) - 2):
            substring = s[i:i+3]
            if len(set(substring)) == 3:
                count += 1
        return count
      
class Solution {
public:
    int countGoodSubstrings(string s) {
        int count = 0;
        for (int i = 0; i + 2 < s.size(); ++i) {
            if (s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]) {
                count++;
            }
        }
        return count;
    }
};
      
class Solution {
    public int countGoodSubstrings(String s) {
        int count = 0;
        for (int i = 0; i <= s.length() - 3; i++) {
            char a = s.charAt(i), b = s.charAt(i+1), c = s.charAt(i+2);
            if (a != b && a != c && b != c) {
                count++;
            }
        }
        return count;
    }
}
      
var countGoodSubstrings = function(s) {
    let count = 0;
    for (let i = 0; i <= s.length - 3; i++) {
        let a = s[i], b = s[i+1], c = s[i+2];
        if (a !== b && a !== c && b !== c) {
            count++;
        }
    }
    return count;
};

Problem Description

Given a string s, you are asked to count the number of substrings of length 3 that consist of all distinct characters. In other words, for every substring of size 3, check if all the characters are different, and count how many such substrings exist.

Key Constraints:
  • Each substring considered must be exactly 3 characters long.
  • All characters in the substring must be unique (no repeats).
  • Substrings can overlap.
  • Input string s consists of lowercase English letters.

Thought Process

Let's break down the problem. We want to look at every group of 3 consecutive characters in s and check if they're all different. The most straightforward way is to check each possible substring of length 3. At first, you might think of generating all substrings, but since we only care about those of length 3, we can just slide a window of size 3 across the string. For each window, check if the three characters are unique. A brute-force approach would be to extract every substring and check for uniqueness by comparing each character. But we can optimize by noting that for just 3 characters, it's easy to compare them directly without extra data structures. If s is very long, we want to avoid unnecessary work. Luckily, checking three characters is constant time, so our sliding window approach is efficient.

Solution Approach

To solve this problem, we use a simple sliding window of size 3. Here’s how to approach it step by step:
  1. Initialize a counter variable to 0. This will store the number of valid substrings.
  2. Loop through the string from index 0 to len(s) - 3 + 1 (so that each window is of size 3).
  3. For each position, extract the substring of length 3.
  4. Check if all three characters in the substring are different. There are two main ways:
    • Compare each character directly (e.g., a != b && a != c && b != c).
    • Alternatively, put the characters in a set and see if its length is 3.
  5. If the substring is valid, increment your counter.
  6. After the loop, return the counter as your answer.
Why this works:
  • We only need to check substrings of length 3, so the window slides one character at a time.
  • Checking three characters for uniqueness is a constant-time operation.
  • No extra space is needed except for a counter and possibly a set of size 3.

Example Walkthrough

Let's walk through the input s = "xyzzaz".
  1. First window: "xyz"
    • Characters: x, y, z (all different)
    • Valid, count = 1
  2. Second window: "yzz"
    • Characters: y, z, z (z repeats)
    • Invalid, count remains 1
  3. Third window: "zza"
    • Characters: z, z, a (z repeats)
    • Invalid, count remains 1
  4. Fourth window: "zaz"
    • Characters: z, a, z (z repeats)
    • Invalid, count remains 1
  5. Fifth window: "az"
    • Not enough characters, so we stop.
Final count is 1.

Time and Space Complexity

  • Brute-force approach: If you generated all substrings and checked each for uniqueness, it would be O(n) for generating substrings (since each is size 3) and O(1) for checking uniqueness. So, overall O(n).
  • Optimized sliding window approach: Still O(n), because you check each window of size 3 once, and the check is constant time.
  • Space complexity: O(1), since at most you store three characters or a set of size 3.
Summary: Both time and space are efficient and scale linearly with the input size.

Summary

The key insight is that you only need to check each group of three consecutive characters for uniqueness, which is a simple and efficient operation. By sliding a window of size 3 and checking directly, you avoid unnecessary computation or memory usage. This makes the solution both easy to implement and optimal for performance.