Find K Length Substrings With No Repeated Characters - Leetcode Solution

Problem Statement:

Given a string, s, find all k length substrings with no repeated characters.

Example:

Input: s = "abcabc", k = 3 Output: ["abc", "bca", "cab"]

Input: s = "abacab", k = 3 Output: ["bac", "aca", "cab"]

Solution:

The problem can be solved using a sliding window technique. We can define two pointers, left and right. We start both pointers at the beginning of the string. We then move the right pointer to the right until we have a substring with k characters. At this point, we check whether all characters are unique. If they are, we add this substring to our answer. If they are not, we move the left pointer to the right and repeat the process until we have exhausted all possible substrings.

Let’s go through the solution step by step:

1. Initialize variables:

   • left = 0
   • right = 0
   • n = length of the string
   • res = empty list to store results

2. Define a dictionary, seen, to store the characters we have seen so far.

3. While right pointer is less than or equal to n - k:

   • Create a substring with k length by slicing the string from right to right + k.
   • If all characters in the substring are unique:
     • Add the substring to the res list.
   • Increment the right pointer by 1 to move the window to the right.
   • Add the character at the new right pointer position to the seen dictionary.

4. If the res list is empty, return an empty list. Otherwise, return the res list.

Here is the Python code for the above solution:

def findKLengthSubstrings(s: str, k: int) -> List[str]:
    left, right, n = 0, 0, len(s)
    res = []
    seen = {}

    while right <= n - k:
        sub = s[right:right+k]
        if len(set(sub)) == k:
            res.append(sub)
        right += 1
        seen[s[right-1]] = seen.get(s[right-1], 0) + 1
        if seen[s[left]] > 1:
            seen[s[left]] -= 1
            left += 1
        else:
            del seen[s[left]]
            left += 1
    
    return res

Note: This code also handles the edge cases where the input string is empty or k is 0.

Time Complexity:

The time complexity of this solution is O(n) where n is the length of the input string.

Space Complexity:

The space complexity of this solution is O(k) where k is the length of the substring.

1