algoadvance

Leetcode 1876. Substrings of Size Three with Distinct Characters

Problem Statement

You are given a string s, and you need to return the number of good substrings of length three. A “good substring” is defined as a substring where all characters are distinct.

Example:

Input: s = "xyzzaz"
Output: 1
Explanation: There are four substrings of size 3: "xyz", "yzz", "zza", and "zaz". 
"xyz" is the only good substring.

Clarifying Questions

  1. What is the length of string s?
    • The length of s can be between 1 and 100, so we’ll consider this in our approach to ensure it runs efficiently even at the upper limit.
  2. Should we consider substrings with different orders of characters?
    • No, the substrings should only be considered “good” if they contain exactly three distinct characters.
  3. What if the length of s is less than 3?
    • In this case, it’s impossible to have a substring of length 3, so we should return 0.

Strategy

We will use a sliding window approach to solve this problem efficiently:

  1. Iterate through the string s using a window of size 3.
  2. Check each window to see if it contains exactly three distinct characters.
  3. Count each window that meets this criterion.
  4. Return the count at the end.

Code

public class Solution {
    public int countGoodSubstrings(String s) {
        if (s.length() < 3) {
            return 0;
        }

        int count = 0;

        for (int i = 0; i <= s.length() - 3; i++) {
            if (isGoodSubstring(s.substring(i, i + 3))) {
                count++;
            }
        }

        return count;
    }

    private boolean isGoodSubstring(String substring) {
        return substring.charAt(0) != substring.charAt(1) &&
               substring.charAt(1) != substring.charAt(2) &&
               substring.charAt(0) != substring.charAt(2);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countGoodSubstrings("xyzzaz")); // Output: 1
        System.out.println(sol.countGoodSubstrings("aababcabc")); // Output: 4
    }
}

Time Complexity

This ensures that our solution is efficient and works within given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI