Problem

A string is good if there are no repeated characters.

Given a string s​​​​​, return _the number ofgood 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.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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.

Solution

Method 1 – Sliding Window

Intuition

Check every substring of length 3 and count it if all characters are distinct. This is efficient since the string is short and the window is small.

Approach

  1. Loop through the string, for each index i from 0 to len(s) - 3:
    • Check if s[i], s[i+1], and s[i+2] are all different.
    • If so, increment the answer.
  2. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int countGoodSubstrings(string s) {
        int ans = 0, n = s.size();
        for (int i = 0; i + 2 < n; ++i) {
            if (s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func countGoodSubstrings(s string) int {
    ans := 0
    n := len(s)
    for i := 0; i+2 < n; i++ {
        if s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2] {
            ans++
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int countGoodSubstrings(String s) {
        int ans = 0, n = s.length();
        for (int i = 0; i + 2 < n; i++) {
            if (s.charAt(i) != s.charAt(i+1) && s.charAt(i) != s.charAt(i+2) && s.charAt(i+1) != s.charAt(i+2)) ans++;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun countGoodSubstrings(s: String): Int {
        var ans = 0
        for (i in 0..s.length-3) {
            if (s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]) ans++
        }
        return ans
    }
}
1
2
3
4
5
6
7

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        ans = 0
        for i in range(len(s) - 2):
            if len(set(s[i:i+3])) == 3:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn count_good_substrings(s: String) -> i32 {
        let s = s.as_bytes();
        let mut ans = 0;
        for i in 0..s.len().saturating_sub(2) {
            if s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2] {
                ans += 1;
            }
        }
        ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    countGoodSubstrings(s: string): number {
        let ans = 0;
        for (let i = 0; i + 2 < s.length; i++) {
            if (s[i] !== s[i+1] && s[i] !== s[i+2] && s[i+1] !== s[i+2]) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each substring of length 3 is checked once.
  • 🧺 Space complexity: O(1) — Only a few variables are used.