1100. Find K-Length Substrings With No Repeated Characters - Explanation

Description

Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.

Example 1:

Input: s = "havefunonneetcode", k = 5

Output: 6

Explanation:

There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

Example 2:

Input: s = "home", k = 5

Output: 0

Explanation: Notice k can be larger than the length of s. In this case, it is not possible to find any substring.

Constraints:

1 <= s.length <= 10^4
s consists of lowercase English letters
1 <= k <= 10^4

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        if k > 26:
            return 0
        answer = 0
        n = len(s)

        for i in range(n - k + 1):
            # Initializing an empty frequency array
            freq = [0] * 26

            for j in range(i, i + k):
                curr_char = ord(s[j]) - ord("a")

                # Incrementing the frequency of current character
                freq[curr_char] += 1

                # If a repeated character is found, we stop the loop
                if freq[curr_char] > 1:
                    break
            else:
                # If the substring does not have any repeated characters,
                # we increment the answer
                answer += 1

        return answer

Time & Space Complexity

Time complexity: $O(n \cdot \min(m, k))$
Space complexity: $O(m)$

Where $n$ is the length of s, $k$ is the given substring length, and $m$ is the number of unique characters allowed in the string. In this case, $m=26$ .

2. Sliding Window

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        # We can reuse the condition from the first approach
        # as for k > 26, there can be no substrings with only unique characters
        if k > 26:
            return 0
        answer = 0
        n = len(s)

        # Initializing the left and right pointers
        left = right = 0

        # Initializing an empty frequency array
        freq = [0] * 26

        # Function to obtain the index of a character according to the alphabet
        def get_val(ch: str) -> int:
            return ord(ch) - ord("a")

        while right < n:

            # Add the current character in the frequency array
            freq[get_val(s[right])] += 1

            # If the current character appears more than once in the frequency array
            # keep contracting the window and removing characters from the
            # frequency array till the frequency of the current character becomes 1.
            while freq[get_val(s[right])] > 1:
                freq[get_val(s[left])] -= 1
                left += 1

            # Check if the length of the current unique substring is equal to k
            if right - left + 1 == k:
                answer += 1

                # Contract the window and remove the leftmost character from the
                # frequency array
                freq[get_val(s[left])] -= 1
                left += 1

            # Expand the window
            right += 1

        return answer

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of s and $m$ is the number of unique characters allowed in the string. In this case, $m=26$ .