Substrings of Size Three with Distinct Characters

Substrings of Size Three with Distinct Characters - 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "xyzzaz"

› Output: 1

💡 Note: Only "xyz" at the beginning has all distinct characters. "yzz", "zza", and "zaz" all have repeated characters.

Example 2 — Multiple Good Substrings

$ Input: s = "aababcabc"

› Output: 4

💡 Note: The good substrings are: "bab" (index 2), "abc" (index 3), "bca" (index 4), "cab" (index 5), "abc" (index 6). Total = 4 distinct character substrings.

Example 3 — No Good Substrings

$ Input: s = "aaa"

› Output: 0

💡 Note: Only one substring "aaa" exists, but it has repeated characters, so no good substrings.

Constraints

1 ≤ s.length ≤ 100
s consists of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

String with characters to analyze

Process

Check each 3-character window for distinct characters

Output

Count of substrings with all unique characters

Key Takeaway

🎯 Key Insight: Check each 3-character window by comparing all pairs - no complex data structures needed

Asked in

a Amazon 25 f Facebook 18 G Google 15 M Microsoft 12

The key insight is that we only need to check if all 3 characters in each substring are distinct by comparing pairs. Best approach is sliding window for clean implementation. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Substring	O(n)	O(1)	Generate all substrings of length 3 and check if characters are distinct
Sliding Window - Optimized Traversal	O(n)	O(1)	Use sliding window to check each 3-character substring efficiently

Brute Force - Check Every Substring — Algorithm Steps

Iterate through each possible starting position (0 to n-3)
Extract substring of length 3
Check if all 3 characters are distinct
Count valid substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Slide Window

Move through each position checking 3 characters

Check Distinct

Compare all pairs to ensure no duplicates

Count Valid

Increment counter for good substrings

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int count = 0;
    int n = strlen(s);
    
    // Check each possible substring of length 3
    for (int i = 0; i <= n - 3; i++) {
        // Check if all characters are distinct
        if (s[i] != s[i+1] && s[i+1] != s[i+2] && s[i] != s[i+2]) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string with constant work per position (checking 3 characters)

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Substring — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler