Substrings of Size Three with Distinct Characters — Easy Problem & Solution

A string is good when it has no repeated characters. Return the number of good substrings of length exactly three in s.

Difficulty: Easy
Topics: Strings, Hash Table, Sliding Window, Counting
Asked at: Amazon, Adobe, Cognizant
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string is good when it has no repeated characters.

Return the number of good substrings of length exactly three in s. Substrings that occur more than once are counted each time.

Example 1

Input: s = "codekairo"
Output: 7
Explanation: Every window of three is good: cod, ode, dek, eka, kai, air, iro.

Example 2

Input: s = "xyzzaz"
Output: 1
Explanation: Only "xyz" has three distinct characters.

Example 3

Input: s = "aababcabc"
Output: 4
Explanation: "abc", "bca", "cab" and "abc" again.

Constraints

1 <= s.length <= 100000
s consists of lowercase English letters.

How to solve Substrings of Size Three with Distinct Characters

With a window this small, the distinctness test is three equality checks, so a direct scan over every window of length three is already linear.

Approach

Walk i from 0 while i + 3 <= |s|.
Check s[i] != s[i+1], s[i+1] != s[i+2] and s[i] != s[i+2].
Count the windows that pass.

Why it works

Three values are pairwise distinct precisely when all three unordered pairs differ; checking only adjacent pairs would accept "aba". Each window costs constant time, so the whole scan is O(n).

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Comparing only neighbouring characters wrongly accepts patterns like "aba".
A string shorter than three characters has no windows and the answer is 0.
Repeated occurrences of the same substring each count — this is not a distinct-substring count.

Reference solution

Python

def countGoodSubstrings(s: str) -> int:
    count = 0
    for i in range(len(s) - 2):
        if s[i] != s[i + 1] and s[i + 1] != s[i + 2] and s[i] != s[i + 2]:
            count += 1
    return count

JavaScript

var countGoodSubstrings = function(s) {
    var count = 0;
    for (var i = 0; i + 3 <= s.length; i++) {
        var a = s.charAt(i), b = s.charAt(i + 1), c = s.charAt(i + 2);
        if (a !== b && b !== c && a !== c) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue