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

Description

https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/

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

Example 1:

Input: s = "havefunonleetcode", 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 is not possible to find any substring.

Note:

  1. 1 <= s.length <= 104
  2. All characters of s are lowercase English letters.
  3. 1 <= k <= 104

Explanation

Iterate each character and check if there is a string with no repeating character at length of k starting from the character.

Python Solution

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        if k > len(s):
            return 0
        
        count = 0
        
        for i in range(len(s) - k + 1):
            visited = set()
            
            for j in range(i, i + k):
                
                c = s[j]
                
                if c in visited:
                    break
                else:                
                    visited.add(c)
                
            if len(visited) == k:
                count += 1
                
                
        return count
                
                
  • Time Complexity: O(N^2).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.