Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Substrings of Size Three with Distinct Characters solution and explanation

EasyCountingHash TableSliding WindowString5 min read77.3% acceptanceUpdated 9 Apr 2026
Asked atQuoraVisaAmazonMicrosoftBloomberg
Practise Substrings of Size Three with Distinct Characters
12:17
Substrings of Size Three with Distinct Characters | Sliding WindowShiva Prasad Gurram · 12:17 · 2K viewsWatch on YouTube
9 more videos on this problem
  1. Substrings of Size Three with Distinct Characters | Sliding WindowShiva Prasad Gurram · 12:17 · 2K views
  2. LeetCode [easy] Substrings of Size Three with Distinct CharactersFrancesco Manicardi · 2:47 · 1K views
  3. 1876. Substrings of Size Three with Distinct Characters (Leetcode Easy)Programming Live with Larry · 2:16 · 1K views
  4. LeetCode 1876. Substrings of Size Three with Distinct Characters JavaScript Sliding WindowSantamaria Code · 8:52 · 653 views
  5. 1876. Substrings of Size Three with Distinct Characters | Leetcode 1876Rg_semicolon · 8:45 · 463 views
  6. LeetCode 1876: Substrings of Size Three with Distinct Characters Made Easy For Complete BeginnersJameSparKing · 2:20 · 336 views
  7. Substrings of Size Three with Distinct Characters | Leetcode 1876 | Approach + Code with explanationPirai's Academy · 13:38 · 185 views
  8. LeetCode 1876 | Substrings of Size Three with Distinct Characters | JavaSleepy Cracker · 1:45 · 171 views
  9. Leetcode 1876 Substrings of Size Three with Distinct CharactersMath Geeks · 2:02 · 155 views
  10. 1876. Substrings of Size Three with Distinct Characters || leetcodecodeWithSaif · 8:05 · 139 views

The problem

A string is good if there are no repeated characters.

Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

Example 1:

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

Example 2:

Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".

Constraints:

  • 1 <= s.length <= 100
  • s​​​​​​ consists of lowercase English letters.

Approach overview

Problem Overview: Given a string s, count how many substrings of length three contain all distinct characters. Each valid substring must have three different characters, meaning no duplicates inside the window.

Approach 1: Naive Enumeration (Time: O(n), Space: O(1))

The direct way is to examine every substring of length three. Iterate through the string from index 0 to n-3, extract the three characters at i, i+1, and i+2, and check whether they are all different. A simple comparison such as a != b, a != c, and b != c verifies uniqueness. Each iteration performs constant work, so the overall time complexity is O(n) and space complexity is O(1). This approach works because the substring length is fixed at three, eliminating the need for dynamic structures like a hash table. It is straightforward and often the quickest implementation during interviews when constraints are small.

Approach 2: Sliding Window Technique (Time: O(n), Space: O(1))

A more general solution uses the sliding window pattern. Maintain a window of size three that moves from left to right across the string. For each window, track character frequencies using a small counter array or map. When the window reaches size three, check whether all counts are 1. If so, the substring contains distinct characters and contributes to the answer. Then slide the window forward by removing the leftmost character and adding the next one on the right.

This method demonstrates a reusable pattern for substring problems. Instead of recomputing uniqueness from scratch, the window updates counts incrementally as it moves. Each character enters and leaves the window at most once, producing linear time complexity O(n). Space usage stays O(1) because the alphabet size is bounded. Problems involving substring counting frequently combine string traversal with frequency tracking and incremental updates.

The sliding window approach becomes especially valuable when the substring size is not fixed or when you must track additional conditions like character frequency limits. It also scales naturally to larger windows or variable-length substring constraints.

Recommended for interviews: The sliding window approach is what interviewers typically expect. The naive method proves you understand the problem and edge cases, but sliding window shows familiarity with a core string-processing pattern. Demonstrating the ability to maintain counts while shifting the window signals strong algorithmic fundamentals.

Approach 1: Naive Approach

This approach involves iterating over the string and extracting all possible substrings of length three. For each substring, we check if it contains all unique characters by employing a set, as sets do not allow duplicate entries.

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

# Example usage
s = "xyzzaz"
print(countGoodSubstrings(s))
public class GoodSubstrings {
    public static int countGoodSubstrings(String s) {
        int count = 0;
        for (int i = 0; i <= s.length() - 3; i++) {
            if (isUnique(s, i)) count++;
        }
        return count;
    }

    private static boolean isUnique(String s, int start) {
        return s.charAt(start) != s.charAt(start + 1) &&
               s.charAt(start) != s.charAt(start + 2) &&
               s.charAt(start + 1) != s.charAt(start + 2);
    }

    public static void main(String[] args) {
        String s = "xyzzaz";
        System.out.println(countGoodSubstrings(s));
    }
}
#include <iostream>
#include <unordered_set>
using namespace std;

bool isUnique(string &s, int start) {
    return s[start] != s[start + 1] && 
           s[start] != s[start + 2] && 
           s[start + 1] != s[start + 2];
}

int countGoodSubstrings(string s) {
    int count = 0;
    for (int i = 0; i <= s.size() - 3; ++i) {
        if (isUnique(s, i)) {
            ++count;
        }
    }
    return count;
}

int main() {
    string s = "xyzzaz";
    cout << countGoodSubstrings(s) << endl;
    return 0;
}
function countGoodSubstrings(s) {
    let count = 0;
    for (let i = 0; i <= s.length - 3; i++) {
        const substring = s.slice(i, i + 3);
        if (new Set(substring).size === 3) count++;
    }
    return count;
}

// Example usage
const s = "xyzzaz";
console.log(countGoodSubstrings(s));
#include <stdio.h>
#include <string.h>

int isUnique(char *str, int start) {
    return str[start] != str[start + 1] && 
           str[start] != str[start + 2] && 
           str[start + 1] != str[start + 2];
}

int countGoodSubstrings(char *s) {
    int count = 0;
    int len = strlen(s);
    for (int i = 0; i <= len - 3; ++i) {
        if (isUnique(s, i)) {
            ++count;
        }
    }
    return count;
}

int main() {
    char s[] = "xyzzaz";
    printf("%d\n", countGoodSubstrings(s));
    return 0;
}
using System;

class Program {
    static int CountGoodSubstrings(string s) {
        int count = 0;
        for (int i = 0; i <= s.Length - 3; i++) {
            if (IsUnique(s, i)) count++;
        }
        return count;
    }

    static bool IsUnique(string s, int start) {
        return s[start] != s[start + 1] &&
               s[start] != s[start + 2] &&
               s[start + 1] != s[start + 2];
    }

    static void Main() {
        string s = "xyzzaz";
        Console.WriteLine(CountGoodSubstrings(s));
    }
}

The Python solution uses slicing to extract substrings and a set to check for unique characters within each substring.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), excluding the space for input storage.

Try this approach in the editor

Approach 2: Sliding Window Technique

This efficient approach uses the sliding window technique to iterate over possible substrings of length three. The sliding window maintains the state of the current substring and checks for uniqueness in constant time as it slides over the string.

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

# Example usage
s = "xyzzaz"
print(countGoodSubstrings(s))
public class GoodSubstrings {
    public static int countGoodSubstrings(String s) {
        int count = 0;
        for (int i = 0; i <= s.length() - 3; i++) {
            if (s.charAt(i) != s.charAt(i + 1) &&
                s.charAt(i) != s.charAt(i + 2) &&
                s.charAt(i + 1) != s.charAt(i + 2)) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s = "xyzzaz";
        System.out.println(countGoodSubstrings(s));
    }
}
#include <iostream>
using namespace std;

bool isUnique(string &s, int i) {
    return s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2];
}

int countGoodSubstrings(string s) {
    int count = 0;
    for (int i = 0; i <= s.size() - 3; ++i) {
        if (isUnique(s, i)) {
            ++count;
        }
    }
    return count;
}

int main() {
    string s = "xyzzaz";
    cout << countGoodSubstrings(s) << endl;
    return 0;
}
function countGoodSubstrings(s) {
    let count = 0;
    for (let i = 0; i <= s.length - 3; i++) {
        if (s[i] !== s[i + 1] && s[i] !== s[i + 2] && s[i + 1] !== s[i + 2])
            count++;
    }
    return count;
}

// Example usage
const s = "xyzzaz";
console.log(countGoodSubstrings(s));
#include <stdio.h>
#include <stdbool.h>

bool isUnique(char* s, int i, int j, int k) {
    return s[i] != s[j] && s[i] != s[k] && s[j] != s[k];
}

int countGoodSubstrings(char* s) {
    int count = 0;
    for (int i = 0; s[i + 2] != '\0'; ++i) {
        if (isUnique(s, i, i+1, i+2)) {
            count++;
        }
    }
    return count;
}

int main() {
    char s[] = "xyzzaz";
    printf("%d\n", countGoodSubstrings(s));
    return 0;
}
using System;

class Program {
    static int CountGoodSubstrings(string s) {
        int count = 0;
        for (int i = 0; i <= s.Length - 3; i++) {
            if (s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2])
                count++;
        }
        return count;
    }

    static void Main() {
        string s = "xyzzaz";
        Console.WriteLine(CountGoodSubstrings(s));
    }
}

The Python program runs a sliding window over the string characters, comparing each adjacent set of three directly, increasing efficiency.

Complexity

Time Complexity: O(n), processing each possible substring once.
Space Complexity: O(1), as no significant extra space is allocated.

Try this approach in the editor

Approach 3: Sliding Window

We can maintain a sliding window such that the characters within the window are not repeated. Initially, we use a binary integer mask of length 26 to represent the characters within the window, where the i-th bit being 1 indicates that character i has appeared in the window, otherwise it indicates that character i has not appeared in the window.

Then, we traverse the string s. For each position r, if s[r] has appeared in the window, we need to move the left boundary l of the window to the right until there are no repeated characters in the window. After this, we add s[r] to the window. At this point, if the length of the window is greater than or equal to 3, then we have found a good substring of length 3 ending at s[r].

After the traversal, we have found the number of all good substrings.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

This solution can be extended to find the number of good substrings of length k.

function countGoodSubstrings(s: string): number {
    let ans = 0;
    const n = s.length;
    for (let l = 0, r = 0, mask = 0; r < n; ++r) {
        const x = s.charCodeAt(r) - 'a'.charCodeAt(0);
        while ((mask >> x) & 1) {
            const y = s.charCodeAt(l++) - 'a'.charCodeAt(0);
            mask ^= 1 << y;
        }
        mask |= 1 << x;
        ans += r - l + 1 >= 3 ? 1 : 0;
    }
    return ans;
}
func countGoodSubstrings(s string) (ans int) {
	mask, l := 0, 0
	for r, c := range s {
		x := int(c - 'a')
		for (mask>>x)&1 == 1 {
			y := int(s[l] - 'a')
			l++
			mask ^= 1 << y
		}
		mask |= 1 << x
		if r-l+1 >= 3 {
			ans++
		}
	}
	return
}
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function countGoodSubstrings($s) {
        $ans = 0;
        $n = strlen($s);
        $l = 0;
        $r = 0;
        $mask = 0;

        while ($r < $n) {
            $x = ord($s[$r]) - ord('a');
            while (($mask >> $x) & 1) {
                $y = ord($s[$l++]) - ord('a');
                $mask ^= 1 << $y;
            }
            $mask |= 1 << $x;
            if ($r - $l + 1 >= 3) {
                $ans++;
            }
            $r++;
        }

        return $ans;
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Naive Approach

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), excluding the space for input storage.

Sliding Window Technique

Time Complexity: O(n), processing each possible substring once.
Space Complexity: O(1), as no significant extra space is allocated.

Sliding Window–

Complexity analysis

ApproachTimeSpaceWhen to Use
Naive EnumerationO(n)O(1)Quick implementation when substring size is fixed and small
Sliding Window TechniqueO(n)O(1)Preferred interview approach; scalable to variable window problems

Frequently asked questions

Is Substrings of Size Three with Distinct Characters easy or hard?

Substrings of Size Three with Distinct Characters is classified as an Easy problem. The logic is straightforward because the substring length is fixed at three. The challenge mainly involves recognizing that a sliding window pattern can generalize the solution.

Substrings of Size Three with Distinct Characters Python/Java solution

In Python or Java, iterate through the string while maintaining a window of length three. Check if the three characters are distinct using comparisons or a small set. The sliding window version updates character counts as the window moves and maintains O(n) time complexity.

How to solve Substrings of Size Three with Distinct Characters in O(n)?

Iterate through the string using a sliding window of length three. Track the characters currently inside the window using a small frequency map or array. If the window contains three unique characters, increment the count. Slide the window forward by removing the left character and adding the next character on the right.

What is the best approach for Substrings of Size Three with Distinct Characters?

The sliding window technique is the preferred approach. Maintain a window of size three and track character frequencies as the window moves across the string. Each step checks whether all characters in the window are unique. This runs in O(n) time and O(1) space and demonstrates a common pattern used in many substring problems.

Is Substrings of Size Three with Distinct Characters asked at Google/Amazon/Meta?

Substring counting problems using sliding window techniques appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying pattern of maintaining a fixed-size window and tracking character frequencies is commonly tested.

What data structure is used in Substrings of Size Three with Distinct Characters?

Most solutions rely on simple character comparisons or a small frequency structure such as an array or hash map. When using the sliding window technique, a frequency array or hash table tracks how many times each character appears inside the current window.

What is the time complexity of Substrings of Size Three with Distinct Characters?

The optimal time complexity is O(n), where n is the length of the string. Each character is processed at most once as the window slides through the string. Space complexity remains O(1) because the algorithm only stores counts for a small fixed alphabet.

Comments

Now write it yourselfClose this page and solve Substrings of Size Three with Distinct Characters in the editor, without looking.
Practise Substrings of Size Three with Distinct Characters