Find K-Length Substrings With No Repeated Characters

Medium · Sliding Window · Explanation and code example

Sliding Window

How it works

Instead of recomputing character frequencies for each substring from scratch, we can maintain a sliding window. As we move the window, we add the new character on the right and remove the character that falls off on the left. When a duplicate is detected, we shrink the window from the left until all characters are unique again.

Steps

  1. If k > 26, return 0 (impossible to have k unique characters).
  2. Initialize two pointers left = 0 and right = 0, and a frequency array.
  3. While right < n:
    • Add s[right] to the frequency array.
    • While the frequency of s[right] exceeds 1, remove s[left] from the window and increment left.
    • If the window size equals k, increment the answer, then shrink the window from the left by one to prepare for the next position.
    • Move right forward.
  4. Return the answer.

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.

Things to watch for

Not Handling k Greater Than 26

Since the string contains only lowercase English letters, it's impossible to have a substring of length greater than 26 with all unique characters. Forgetting to add an early return for k > 26 leads to unnecessary computation or incorrect results when the problem guarantees such substrings cannot exist.

Incorrect Window Shrinking Logic

In the sliding window approach, when a duplicate character is found, you must shrink the window from the left until the duplicate is removed. A common mistake is shrinking by exactly one position or shrinking until the window size is less than k. The correct approach is to shrink until the frequency of the newly added character becomes 1.

Off-by-One Errors in Loop Bounds

When iterating through possible starting positions for substrings of length k, the loop should run from 0 to n - k (inclusive). Using n - k + 1 as the upper bound or forgetting the inclusive boundary leads to either missing valid substrings or accessing indices out of bounds.

Python code example

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

C++ code example

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        // 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;

        int answer = 0;
        int n = s.size();

        // Initializing the left and right pointers
        int left = 0, right = 0;
        // Initializing an empty frequency array
        int freq[26] = {0};

        while (right < n) {
            // Add the current character in the frequency array
            freq[s[right] - 'a']++;

            // 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[s[right] - 'a'] > 1) {
                freq[s[left] - 'a']--;
                left++;
            }

            // Check if the length of the current unique substring is equal to k
            if (right - left + 1 == k) {
                answer++;

                // Contract the window and remove the leftmost character from
                // the frequency array
                freq[s[left] - 'a']--;
                left++;
            }

            // Expand the window
            right++;
        }

        return answer;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations