Jobs

Interviews

Discussions

Find Longest Self-Contained Substring

Hard

Asked by:

30 views

Topics:

StringsSliding Windows

You are given a string s consisting of lowercase English letters. A substring of s is considered self-contained if it contains each of its distinct characters the same number of times.

For example, "aabb" is self-contained because both 'a' and 'b' appear twice. "aab" is not self-contained because 'a' appears twice, while 'b' appears only once.

Return the length of the longest self-contained substring of s.

Example 1:


Input: s = "aabcbc"
Output: 6
Explanation: The longest self-contained substring is "aabcbc" because 'a', 'b', and 'c' each appear twice.

Example 2:


Input: s = "abcabcbb"
Output: 0
Explanation: There are no self-contained substrings in this example.

Example 3:


Input: s = "abababab"
Output: 8
Explanation: The entire string is self-contained as both 'a' and 'b' appear four times.

Constraints:

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

Try coding it in LeetCode

Find Longest Self-Contained Substring

Hard

Asked by:

30 views

Topics:

StringsSliding Windows

You are given a string s consisting of lowercase English letters. A substring of s is considered self-contained if it contains each of its distinct characters the same number of times.

For example, "aabb" is self-contained because both 'a' and 'b' appear twice. "aab" is not self-contained because 'a' appears twice, while 'b' appears only once.

Return the length of the longest self-contained substring of s.

Example 1:


Input: s = "aabcbc"
Output: 6
Explanation: The longest self-contained substring is "aabcbc" because 'a', 'b', and 'c' each appear twice.

Example 2:


Input: s = "abcabcbb"
Output: 0
Explanation: There are no self-contained substrings in this example.

Example 3:


Input: s = "abababab"
Output: 8
Explanation: The entire string is self-contained as both 'a' and 'b' appear four times.

Constraints:

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

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:

Can the input string be empty or null?
What characters can the string contain (e.g., ASCII, Unicode)?
What should be returned if no self-contained substring is found?
Is the substring case-sensitive?
Could you define more precisely what you mean by 'self-contained' in this context? Specifically, what determines that a substring is or is not 'self-contained'?

Brute Force Solution

Approach

The brute force approach to finding the longest self-contained substring involves checking every possible substring within the given string. We'll examine all possible starting points and ending points to identify valid substrings. By looking at all the substrings, we can then determine the longest one that meets the requirements.

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

Start by considering a substring of length one, beginning at the very start of the string.
Then, look at a substring of length one, but starting at the second position in the string. Continue this, looking at all substrings of length one in all possible positions.
Next, repeat the process but now with substrings of length two. Start at the beginning of the string, then the second position, and so on.
Keep increasing the length of the substrings you are examining, and repeat the process of shifting the start position for each length.
For each substring you encounter, check if it meets the specific criteria of being 'self-contained' (based on the problem definition).
As you examine each substring, keep track of the longest 'self-contained' substring found so far.
Once you've checked all possible substrings of all possible lengths and start positions, the substring you have been keeping track of is the answer.

Code Implementation

def find_longest_self_contained_substring_brute_force(input_string): 
    longest_substring_found = ""
    input_string_length = len(input_string)

    for substring_length in range(1, input_string_length + 1): 
        for start_index in range(input_string_length - substring_length + 1): 
            end_index = start_index + substring_length
            current_substring = input_string[start_index:end_index]

            # Check if the current substring is self-contained.  The actual logic for checking if a substring is self-contained
            # would go here based on the problem's specific definition. This example assumes any substring is self-contained.
            is_self_contained = True 

            if is_self_contained: 
                #Update if current substring is longer than the existing one
                if len(current_substring) > len(longest_substring_found): 
                    longest_substring_found = current_substring

    return longest_substring_found

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible substrings. There are O(n²) possible substrings since we have two nested loops to define the start and end indices of each substring. For each of these substrings, we then perform a check to determine if it's 'self-contained' which can take up to O(n) time in the worst case, as the self-contained check needs to iterate over the substring. Therefore, the overall time complexity is O(n² * n), which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach iterates through all possible substrings, but it does not explicitly create any auxiliary data structures that scale with the input string's length N. The algorithm only needs to store a few variables, such as the starting and ending indices of the current substring, and the longest self-contained substring found so far. These variables consume a constant amount of space irrespective of the input size N, resulting in constant auxiliary space.

Optimal Solution

Approach

We want to find the longest part of a string where the count of each character is the same. The optimal approach keeps track of these counts and uses a clever way to quickly identify matching sections without comparing every possible start and end point. This avoids unnecessary work, making the process faster and more efficient.

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

Begin by tracking how many times each character appears as you go through the string from left to right.
Use a special system to represent the combination of counts for each character at each point in the string. Think of it like a unique fingerprint for that position.
Store these 'fingerprints' and their locations as you calculate them.
As you continue, look for any repeat 'fingerprints'. When you find a match, it means the section of the string between those two points has an equal number of each character.
Keep track of the longest matching section you've found so far.
Continue through the entire string, and when you're done, the longest matching section you tracked is your answer.

Code Implementation

def find_longest_self_contained_substring(input_string):
    longest_substring_length = 0
    string_length = len(input_string)
    character_count_map = {}
    count_fingerprint_map = {(): -1}

    for index in range(string_length):
        character = input_string[index]
        character_count_map[character] = character_count_map.get(character, 0) + 1
        
        character_counts = tuple(sorted(character_count_map.items()))

        # Store the 'fingerprint' and its index if not already present
        if character_counts not in count_fingerprint_map:
            count_fingerprint_map[character_counts] = index
        else:
            #If fingerprint exists, calculate length
            current_length = index - count_fingerprint_map[character_counts]

            longest_substring_length = max(longest_substring_length, current_length)

    return longest_substring_length

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the string of length n once to calculate and store character counts. A hash map is used to store and retrieve the 'fingerprints' (character count combinations) in O(1) average time. Finding matching fingerprints involves a constant-time lookup. Therefore, the overall time complexity is dominated by the single iteration through the string, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a hash map to store the 'fingerprints' (combinations of character counts) and their locations. In the worst-case scenario, where no two substrings have the same character counts, we would store a fingerprint for each position in the string. Therefore, the space used by the hash map grows linearly with the input size N, where N is the length of the string. This results in an auxiliary space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or null to indicate no substring is found; clarify the expected behavior with the interviewer.
String containing only one character	Return the single character string as it's the longest self-contained substring or return an empty string if the problem specifies a minimum length of 2.
String with all same characters (e.g., 'aaaa')	The algorithm should correctly identify that no self-contained substring exists (unless the entire string is considered self-contained based on problem definition) and return an empty string or the entire string appropriately.
Maximum length string (considering memory constraints)	Ensure the solution's memory usage (e.g., substrings stored, data structures) remains within reasonable limits for large inputs, considering potential out-of-memory errors.
String with unicode or special characters	The algorithm should handle unicode characters correctly, ensuring that character comparisons and substring operations function as intended with multi-byte characters.
String with only delimiters or separators	If delimiters are not valid characters within a self-contained substring, the solution should return an empty string or null.
Overlapping self-contained substrings, requiring the longest	The algorithm must track and compare the length of all identified self-contained substrings to return only the longest one.
Case sensitivity differences if the problem defines case insensitivity	The solution should normalize all characters to either lowercase or uppercase before comparison if case-insensitivity is a requirement of self-containment.

Null or empty input string

How to Handle:

Return an empty string or null to indicate no substring is found; clarify the expected behavior with the interviewer.

String containing only one character

How to Handle:

Return the single character string as it's the longest self-contained substring or return an empty string if the problem specifies a minimum length of 2.

String with all same characters (e.g., 'aaaa')

How to Handle:

The algorithm should correctly identify that no self-contained substring exists (unless the entire string is considered self-contained based on problem definition) and return an empty string or the entire string appropriately.

Maximum length string (considering memory constraints)

How to Handle:

Ensure the solution's memory usage (e.g., substrings stored, data structures) remains within reasonable limits for large inputs, considering potential out-of-memory errors.

String with unicode or special characters

How to Handle:

The algorithm should handle unicode characters correctly, ensuring that character comparisons and substring operations function as intended with multi-byte characters.

String with only delimiters or separators

How to Handle:

If delimiters are not valid characters within a self-contained substring, the solution should return an empty string or null.

Overlapping self-contained substrings, requiring the longest

How to Handle:

The algorithm must track and compare the length of all identified self-contained substrings to return only the longest one.

Case sensitivity differences if the problem defines case insensitivity

How to Handle:

The solution should normalize all characters to either lowercase or uppercase before comparison if case-insensitivity is a requirement of self-containment.

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:

Can the input string be empty or null?
What characters can the string contain (e.g., ASCII, Unicode)?
What should be returned if no self-contained substring is found?
Is the substring case-sensitive?
Could you define more precisely what you mean by 'self-contained' in this context? Specifically, what determines that a substring is or is not 'self-contained'?

Brute Force Solution

Approach

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

Start by considering a substring of length one, beginning at the very start of the string.
Then, look at a substring of length one, but starting at the second position in the string. Continue this, looking at all substrings of length one in all possible positions.
Next, repeat the process but now with substrings of length two. Start at the beginning of the string, then the second position, and so on.
Keep increasing the length of the substrings you are examining, and repeat the process of shifting the start position for each length.
For each substring you encounter, check if it meets the specific criteria of being 'self-contained' (based on the problem definition).
As you examine each substring, keep track of the longest 'self-contained' substring found so far.
Once you've checked all possible substrings of all possible lengths and start positions, the substring you have been keeping track of is the answer.

Code Implementation

def find_longest_self_contained_substring_brute_force(input_string): 
    longest_substring_found = ""
    input_string_length = len(input_string)

    for substring_length in range(1, input_string_length + 1): 
        for start_index in range(input_string_length - substring_length + 1): 
            end_index = start_index + substring_length
            current_substring = input_string[start_index:end_index]

            # Check if the current substring is self-contained.  The actual logic for checking if a substring is self-contained
            # would go here based on the problem's specific definition. This example assumes any substring is self-contained.
            is_self_contained = True 

            if is_self_contained: 
                #Update if current substring is longer than the existing one
                if len(current_substring) > len(longest_substring_found): 
                    longest_substring_found = current_substring

    return longest_substring_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Begin by tracking how many times each character appears as you go through the string from left to right.
Use a special system to represent the combination of counts for each character at each point in the string. Think of it like a unique fingerprint for that position.
Store these 'fingerprints' and their locations as you calculate them.
As you continue, look for any repeat 'fingerprints'. When you find a match, it means the section of the string between those two points has an equal number of each character.
Keep track of the longest matching section you've found so far.
Continue through the entire string, and when you're done, the longest matching section you tracked is your answer.

Code Implementation

def find_longest_self_contained_substring(input_string):
    longest_substring_length = 0
    string_length = len(input_string)
    character_count_map = {}
    count_fingerprint_map = {(): -1}

    for index in range(string_length):
        character = input_string[index]
        character_count_map[character] = character_count_map.get(character, 0) + 1
        
        character_counts = tuple(sorted(character_count_map.items()))

        # Store the 'fingerprint' and its index if not already present
        if character_counts not in count_fingerprint_map:
            count_fingerprint_map[character_counts] = index
        else:
            #If fingerprint exists, calculate length
            current_length = index - count_fingerprint_map[character_counts]

            longest_substring_length = max(longest_substring_length, current_length)

    return longest_substring_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or null to indicate no substring is found; clarify the expected behavior with the interviewer.
String containing only one character	Return the single character string as it's the longest self-contained substring or return an empty string if the problem specifies a minimum length of 2.
String with all same characters (e.g., 'aaaa')	The algorithm should correctly identify that no self-contained substring exists (unless the entire string is considered self-contained based on problem definition) and return an empty string or the entire string appropriately.
Maximum length string (considering memory constraints)	Ensure the solution's memory usage (e.g., substrings stored, data structures) remains within reasonable limits for large inputs, considering potential out-of-memory errors.
String with unicode or special characters	The algorithm should handle unicode characters correctly, ensuring that character comparisons and substring operations function as intended with multi-byte characters.
String with only delimiters or separators	If delimiters are not valid characters within a self-contained substring, the solution should return an empty string or null.
Overlapping self-contained substrings, requiring the longest	The algorithm must track and compare the length of all identified self-contained substrings to return only the longest one.
Case sensitivity differences if the problem defines case insensitivity	The solution should normalize all characters to either lowercase or uppercase before comparison if case-insensitivity is a requirement of self-containment.

Null or empty input string

How to Handle:

Return an empty string or null to indicate no substring is found; clarify the expected behavior with the interviewer.

String containing only one character

How to Handle:

Return the single character string as it's the longest self-contained substring or return an empty string if the problem specifies a minimum length of 2.

String with all same characters (e.g., 'aaaa')

How to Handle:

Maximum length string (considering memory constraints)

How to Handle:

Ensure the solution's memory usage (e.g., substrings stored, data structures) remains within reasonable limits for large inputs, considering potential out-of-memory errors.

String with unicode or special characters

How to Handle:

The algorithm should handle unicode characters correctly, ensuring that character comparisons and substring operations function as intended with multi-byte characters.

String with only delimiters or separators

How to Handle:

If delimiters are not valid characters within a self-contained substring, the solution should return an empty string or null.

Overlapping self-contained substrings, requiring the longest

How to Handle:

The algorithm must track and compare the length of all identified self-contained substrings to return only the longest one.

Case sensitivity differences if the problem defines case insensitivity

How to Handle:

The solution should normalize all characters to either lowercase or uppercase before comparison if case-insensitivity is a requirement of self-containment.