Leetcode 1876: Substrings of Size Three with Distinct Characters

In this problem (https://leetcode.com/problems/substrings-of-size-three-with-distinct-characters/), we want to count the number of substring of length 3(i.e. 3 characters in a row in the string), such that these substring don’t contain duplicate characters.

Given n the length of the input string, we can solve the problem by testing all the substrings of length 3. The number of substrings of length 3 is n — 2, that is O(n). For each of the substring, we only need to compare the 3 characters with 3 comparisons, that is O(1).

class Solution {
    public int countGoodSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            char a = s.charAt(i);
            char b = s.charAt(i + 1);
            char c = s.charAt(i + 2);
            if (a != b && b != c && a != c) {
                count++;
            }
        }
        return count;
    }
}

There might be some more efficient ways to avoid repeating the comparisons between consecutive characters in some cases. It would be interesting to see. However, the result will still be O(n), since I gather you will need at the very least n/2 — 2 comparisons if all the characters of the string are the same.