Substrings of Size Three with Distinct Characters

Easy
781.

Substrings of Size Three with Distinct Characters

Substrings of Size Three with Distinct Characters is an easy coding problem on strings, hash table and counting, asked in Amazon, Adobe and Cognizant interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var countGoodSubstrings = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Substrings of Size Three with Distinct Characters — Solution

Substrings of Size Three with Distinct Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Substrings of Size Three with Distinct Characters is an easy coding problem on strings, hash table and counting, asked in Amazon, Adobe and Cognizant interviews.

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.

Hints for Substrings of Size Three with Distinct Characters

  1. Hint 1

    The window is fixed at three characters, so there are at most n - 2 of them.

  2. Hint 2

    Three characters are distinct exactly when all three pairwise comparisons differ.

  3. Hint 3

    No tally is needed at this size — three comparisons per window is enough.

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

  1. Walk i from 0 while i + 3 <= |s|.
  2. Check s[i] != s[i+1], s[i+1] != s[i+2] and s[i] != s[i+2].
  3. 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

Java

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

C++

int countGoodSubstrings(string s) {
    int count = 0;
    for (int i = 0; i + 3 <= (int) s.size(); i++) {
        if (s[i] != s[i + 1] && s[i + 1] != s[i + 2] && s[i] != s[i + 2]) count++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets