Jobs

Interviews

Discussions

Find K-Length Substrings With No Repeated Characters

Medium

Asked by:

16 views

Topics:

StringsSliding Windows

Given a string s and an integer k, find 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 of length 5 with no repeated characters:
- havef
- avefu
- vefun
- efuno
- funon
- unonl
leetcode

Example 2:

Input: s = "home", k = 5
Output: 0
Explanation:
There are 0 substrings of length 5 in the string "home".

Constraints:

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

Try coding it in LeetCode

Find K-Length Substrings With No Repeated Characters

Medium

Asked by:

16 views

Topics:

StringsSliding Windows

Given a string s and an integer k, find 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 of length 5 with no repeated characters:
- havef
- avefu
- vefun
- efuno
- funon
- unonl
leetcode

Example 2:

Input: s = "home", k = 5
Output: 0
Explanation:
There are 0 substrings of length 5 in the string "home".

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s` and the range for `k`?
Is the input string `s` guaranteed to contain only ASCII characters, or should I consider the full Unicode range?
If no K-length substring with no repeated characters exists, what should I return (e.g., an empty list, null, or a specific error code)?
Should the returned substrings be unique? If the same valid substring appears multiple times, should it be included multiple times in the output?
Is `k` always a positive integer and is it always less than or equal to the length of the input string `s`?

Brute Force Solution

Approach

The brute force strategy for this problem involves examining every possible substring of a specified length within the given string. We check each of these substrings to determine if it contains any repeated characters. If a substring has the correct length and no repeated characters, we count it.

Here's how the algorithm would work step-by-step:

Start by looking at the first possible substring of the desired length in the main string.
Check if all the characters within this substring are unique; that is, make sure no character appears more than once.
If there are no repeated characters, then we found one of the substrings we are looking for, and we mark it.
Next, shift the substring one position to the right and consider that substring.
Again, check if all the characters in this new substring are unique.
Repeat the process of shifting the substring and checking for unique characters until you have examined all possible substrings of the specified length within the main string.
Finally, count the number of substrings that had unique characters, which is our final answer.

Code Implementation

def find_substrings_with_no_repeated_characters_brute_force(main_string, substring_length):
    number_of_substrings_found = 0

    # Iterate through all possible starting positions of substrings
    for index in range(len(main_string) - substring_length + 1):
        substring = main_string[index:index + substring_length]

        # Use a set to track characters, checking for repeats
        character_set = set()
        has_repeated_characters = False

        for character in substring:
            # If char already in set, it's a repeat; break
            if character in character_set:
                has_repeated_characters = True
                break

            character_set.add(character)

        # Increment the counter if no repeats were found
        if not has_repeated_characters:
            number_of_substrings_found += 1

    return number_of_substrings_found

Big(O) Analysis

Time Complexity

O(n*k) – The outer loop iterates through the string of length n, creating substrings of length k. For each substring, we check for repeated characters. This check requires examining each character within the substring, which takes O(k) time. Since we iterate through approximately n possible starting positions for the substring and perform an O(k) operation in each iteration, the overall time complexity is O(n*k).

Space Complexity

O(K) – The provided solution, as described, iterates through substrings of length K and checks for repeated characters within each substring. To determine if a substring has unique characters, we'll likely use an auxiliary data structure such as a set or a frequency map to store the characters encountered in the current substring. This data structure will, at most, store K distinct characters, where K is the length of the substring. Therefore, the space complexity is proportional to K.

Optimal Solution

Approach

We want to find all the small pieces of the big string that have the right length and contain only unique letters. Instead of checking every possible piece, we'll use a 'sliding window' which helps us efficiently check each part once.

Here's how the algorithm would work step-by-step:

Imagine a window that's exactly the right length. We'll slide this window along the big string, one step at a time.
When the window is in a new position, check if all the letters inside that window are different. We can use a tool to quickly tell if there are repeats.
If the window has all different letters, count it as one of our answers.
Slide the window one position to the right and repeat. By sliding and checking this way, we look at each valid piece of the string without doing extra work.

Code Implementation

def find_k_length_substrings_with_no_repeated_characters(input_string, substring_length):
    string_length = len(input_string)
    if substring_length > string_length:
        return 0

    substring_count = 0

    for i in range(string_length - substring_length + 1):
        substring = input_string[i:i + substring_length]

        # Use a set to efficiently detect repeated characters.
        if len(set(substring)) == substring_length:

            substring_count += 1

    return substring_count

Big(O) Analysis

Time Complexity

O(n) – The solution involves sliding a window of size k across the input string of length n. For each window position, we check if the characters within the window are unique. While checking for unique characters *could* take O(k) time using a set or a similar data structure, we are assuming that k is constant or at least significantly smaller than n. Since we slide the window at most n-k+1 times, and for each slide, the work we do is considered constant given the assumptions about k, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a 'sliding window' and checks for unique characters within that window. To detect repeated characters, it implicitly uses a data structure of fixed size, proportional to the alphabet size, not the input string length. Since the alphabet size is constant (e.g., 26 for lowercase English letters), the space used for checking uniqueness within the window is constant regardless of the input string's length N. Thus, the auxiliary space used remains constant, making the space complexity O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list immediately as there are no substrings to process.
K is zero or negative	Return an empty list as a substring of non-positive length is not meaningful.
K is greater than the length of the input string	Return an empty list, because no substring of length K can exist in the string.
Input string contains non-ASCII characters (Unicode)	The character frequency map must handle the full range of Unicode characters correctly, potentially requiring a larger data structure.
All characters in the input string are the same	Return an empty list because if all characters are identical no substring of length greater than 1 can be composed of distinct chars.
Input string is very long and K is relatively small	The sliding window approach should scale linearly with the length of the input string.
Input string contains many overlapping valid substrings	The algorithm must correctly identify and return all valid substrings, without missing any due to the sliding window process.
K is 1	Return a list of each individual character of the input string, as each single character substring is inherently unique.

Null or empty input string

How to Handle:

Return an empty list immediately as there are no substrings to process.

K is zero or negative

How to Handle:

Return an empty list as a substring of non-positive length is not meaningful.

K is greater than the length of the input string

How to Handle:

Return an empty list, because no substring of length K can exist in the string.

Input string contains non-ASCII characters (Unicode)

How to Handle:

The character frequency map must handle the full range of Unicode characters correctly, potentially requiring a larger data structure.

All characters in the input string are the same

How to Handle:

Return an empty list because if all characters are identical no substring of length greater than 1 can be composed of distinct chars.

Input string is very long and K is relatively small

How to Handle:

The sliding window approach should scale linearly with the length of the input string.

Input string contains many overlapping valid substrings

How to Handle:

The algorithm must correctly identify and return all valid substrings, without missing any due to the sliding window process.

K is 1

How to Handle:

Return a list of each individual character of the input string, as each single character substring is inherently unique.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s` and the range for `k`?
Is the input string `s` guaranteed to contain only ASCII characters, or should I consider the full Unicode range?
If no K-length substring with no repeated characters exists, what should I return (e.g., an empty list, null, or a specific error code)?
Should the returned substrings be unique? If the same valid substring appears multiple times, should it be included multiple times in the output?
Is `k` always a positive integer and is it always less than or equal to the length of the input string `s`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first possible substring of the desired length in the main string.
Check if all the characters within this substring are unique; that is, make sure no character appears more than once.
If there are no repeated characters, then we found one of the substrings we are looking for, and we mark it.
Next, shift the substring one position to the right and consider that substring.
Again, check if all the characters in this new substring are unique.
Repeat the process of shifting the substring and checking for unique characters until you have examined all possible substrings of the specified length within the main string.
Finally, count the number of substrings that had unique characters, which is our final answer.

Code Implementation

def find_substrings_with_no_repeated_characters_brute_force(main_string, substring_length):
    number_of_substrings_found = 0

    # Iterate through all possible starting positions of substrings
    for index in range(len(main_string) - substring_length + 1):
        substring = main_string[index:index + substring_length]

        # Use a set to track characters, checking for repeats
        character_set = set()
        has_repeated_characters = False

        for character in substring:
            # If char already in set, it's a repeat; break
            if character in character_set:
                has_repeated_characters = True
                break

            character_set.add(character)

        # Increment the counter if no repeats were found
        if not has_repeated_characters:
            number_of_substrings_found += 1

    return number_of_substrings_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine a window that's exactly the right length. We'll slide this window along the big string, one step at a time.
When the window is in a new position, check if all the letters inside that window are different. We can use a tool to quickly tell if there are repeats.
If the window has all different letters, count it as one of our answers.
Slide the window one position to the right and repeat. By sliding and checking this way, we look at each valid piece of the string without doing extra work.

Code Implementation

def find_k_length_substrings_with_no_repeated_characters(input_string, substring_length):
    string_length = len(input_string)
    if substring_length > string_length:
        return 0

    substring_count = 0

    for i in range(string_length - substring_length + 1):
        substring = input_string[i:i + substring_length]

        # Use a set to efficiently detect repeated characters.
        if len(set(substring)) == substring_length:

            substring_count += 1

    return substring_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list immediately as there are no substrings to process.
K is zero or negative	Return an empty list as a substring of non-positive length is not meaningful.
K is greater than the length of the input string	Return an empty list, because no substring of length K can exist in the string.
Input string contains non-ASCII characters (Unicode)	The character frequency map must handle the full range of Unicode characters correctly, potentially requiring a larger data structure.
All characters in the input string are the same	Return an empty list because if all characters are identical no substring of length greater than 1 can be composed of distinct chars.
Input string is very long and K is relatively small	The sliding window approach should scale linearly with the length of the input string.
Input string contains many overlapping valid substrings	The algorithm must correctly identify and return all valid substrings, without missing any due to the sliding window process.
K is 1	Return a list of each individual character of the input string, as each single character substring is inherently unique.

Null or empty input string

How to Handle:

Return an empty list immediately as there are no substrings to process.

K is zero or negative

How to Handle:

Return an empty list as a substring of non-positive length is not meaningful.

K is greater than the length of the input string

How to Handle:

Return an empty list, because no substring of length K can exist in the string.

Input string contains non-ASCII characters (Unicode)

How to Handle:

The character frequency map must handle the full range of Unicode characters correctly, potentially requiring a larger data structure.

All characters in the input string are the same

How to Handle:

Return an empty list because if all characters are identical no substring of length greater than 1 can be composed of distinct chars.

Input string is very long and K is relatively small

How to Handle:

The sliding window approach should scale linearly with the length of the input string.

Input string contains many overlapping valid substrings

How to Handle:

The algorithm must correctly identify and return all valid substrings, without missing any due to the sliding window process.

K is 1

How to Handle:

Return a list of each individual character of the input string, as each single character substring is inherently unique.