Scale Engineer

Substrings of Size Three with Distinct Characters

Easy
#1712Time: O(N), where `N` is the length of the string `s`. The loop runs `N-2` times. Inside the loop, creating a substring of length 3 and checking its uniqueness with a `HashSet` takes constant time (`O(1)`), as the size is fixed at 3.Space: O(1). Although a `HashSet` and a new `String` object are created in each iteration, their size is constant (at most 3 elements), so the space complexity does not scale with the input size `N`.3 companies
Patterns
Sliding WindowCounting
Data structures
Hash TableString
Companies
AccentureVisaQuora

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the string to generate all substrings of length three. For each substring, a helper function is used to determine if it's "good". This helper function leverages a HashSet to efficiently check for duplicate characters. While this method is versatile and can be adapted for substrings of any length, it introduces some overhead for the specific case of length three.

Algorithm

  • Initialize a counter count to 0.
  • If the string length n is less than 3, return 0.
  • Iterate with an index i from 0 to n - 3.
  • In each iteration, extract the substring of length 3 starting at i.
  • Check if this substring has unique characters using a HashSet:
    • Create an empty HashSet.
    • For each character in the substring, try to add it to the set.
    • If add ever returns false, the substring is not good.
    • If all characters are added successfully, the substring is good.
  • If the substring is good, increment count.
  • Return count after the loop.

Walkthrough

The main logic iterates from the beginning of the string up to the third-to-last character to define the starting point of each potential substring. In each step, a substring of length 3 is extracted. This substring is passed to a helper function, isGood. The isGood function creates a HashSet of characters. It then iterates through the three characters of the substring. For each character, it tries to add it to the set. The add method of a HashSet returns false if the element is already present. If a duplicate is found, isGood immediately returns false. If all characters are added successfully, it means they are all unique, and the function returns true. A counter is incremented for every "good" substring found. Finally, the total count is returned.

import java.util.HashSet;import java.util.Set; class Solution {    private boolean isGood(String sub) {        Set<Character> charSet = new HashSet<>();        for (char c : sub.toCharArray()) {            if (!charSet.add(c)) { // Found a duplicate                return false;            }        }        return true;    }     public int countGoodSubstrings(String s) {        int n = s.length();        if (n < 3) {            return 0;        }        int count = 0;        for (int i = 0; i <= n - 3; i++) {            // Extracting substring can have overhead            String sub = s.substring(i, i + 3);            if (isGood(sub)) {                count++;            }        }        return count;    }}

Complexity

Time

O(N), where `N` is the length of the string `s`. The loop runs `N-2` times. Inside the loop, creating a substring of length 3 and checking its uniqueness with a `HashSet` takes constant time (`O(1)`), as the size is fixed at 3.

Space

O(1). Although a `HashSet` and a new `String` object are created in each iteration, their size is constant (at most 3 elements), so the space complexity does not scale with the input size `N`.

Trade-offs

Pros

  • The logic is clear and easy to reason about.

  • The helper function isGood is modular and can be reused to check substrings of any length k.

Cons

  • Incurs overhead from creating new String and HashSet objects in every iteration.

  • For a fixed small size like 3, this is less performant than direct character comparisons.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem