Jobs

Interviews

Discussions

Maximum Length Substring With Two Occurrences

Easy

Asked by:

39 views

Topics:

ArraysTwo PointersSliding WindowsStrings

Given a string s, return the maximum length of a substring such that it contains at most two occurrences of each character.

Example 1:

Input: s = "bcbbbcba"

Output: 4

Explanation:

The following substring has a length of 4 and contains at most two occurrences of each character: "bcbbbcba".

Example 2:

Input: s = "aaaa"

Output: 2

Explanation:

The following substring has a length of 2 and contains at most two occurrences of each character: "aaaa".

Constraints:

2 <= s.length <= 100
s consists only of lowercase English letters.

Try coding it in LeetCode

Maximum Length Substring With Two Occurrences

Easy

Asked by:

39 views

Topics:

ArraysTwo PointersSliding WindowsStrings

Given a string s, return the maximum length of a substring such that it contains at most two occurrences of each character.

Example 1:

Input: s = "bcbbbcba"

Output: 4

Explanation:

The following substring has a length of 4 and contains at most two occurrences of each character: "bcbbbcba".

Example 2:

Input: s = "aaaa"

Output: 2

Explanation:

The following substring has a length of 2 and contains at most two occurrences of each character: "aaaa".

Constraints:

2 <= s.length <= 100
s consists only 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:

What is the maximum length of the input string `s`?
If no substring appears exactly twice, what should the function return?
Are overlapping occurrences of the substring allowed or disallowed?
Is the string `s` case-sensitive? In other words, should I consider "abc" and "Abc" as the same substring?
Can the input string `s` be empty or null?

Brute Force Solution

Approach

The brute force method for finding the longest substring that appears twice in a larger string involves checking every possible substring. We'll generate all possible substrings and then verify if each substring appears at least two times in the original string. Finally, we'll keep track of the longest substring that meets our criteria.

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

Start by picking a possible substring length, beginning with the longest possible length and working our way down to shorter ones.
For each length, generate every possible substring of that length from the original string.
For each substring, check how many times it appears in the original string.
If a substring appears at least two times, compare its length with the current longest substring found so far.
If the current substring is longer, update the longest substring found.
After checking all possible substrings and lengths, the last longest substring found is the answer.

Code Implementation

def find_maximum_length_substring_with_two_occurrences(text):
    maximum_length = 0
    result_substring = ""

    # Iterate through all possible substring lengths
    for substring_length in range(1, len(text) + 1):

        # Iterate through all possible starting positions for substrings
        for starting_index in range(len(text) - substring_length + 1):
            substring = text[starting_index:starting_index + substring_length]
            occurrence_count = 0

            # Count how many times the current substring appears in the text
            for i in range(len(text) - substring_length + 1):
                if text[i:i + substring_length] == substring:
                    occurrence_count += 1

            # Check if the substring appears exactly twice
            if occurrence_count == 2:

                # Update the longest substring if necessary
                if substring_length > maximum_length:
                    maximum_length = substring_length
                    result_substring = substring

    return result_substring

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through possible substring lengths from n (the length of the string) down to 1. For each length l, it extracts all possible substrings of that length, which is an O(n) operation. Then, for each substring, it searches the entire original string to count occurrences, which is another O(n) operation. Therefore, the overall time complexity is O(n) * O(n) * O(n) which simplifies to O(n^3).

Space Complexity

O(1) – The provided brute force method checks all possible substrings and their occurrences. While generating each substring, we're primarily dealing with comparing string slices or creating temporary string objects representing the substring for comparison. These temporary string objects or slices are created and discarded within each iteration and do not depend on the length of the input string N. Therefore, the auxiliary space required remains constant, using a fixed number of variables regardless of the input string's size. This leads to a space complexity of O(1).

Optimal Solution

Approach

The most efficient way to find the longest substring appearing twice is to check for substrings in reverse order of length. This strategy avoids redundant checks by stopping as soon as the longest possible substring is found. We leverage a method to quickly check the number of occurrences of a substring in the original string.

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

Begin by assuming the entire input string could be our answer and progressively shorten it.
Start by looking for a substring that's just one character smaller than the entire input string. Try all possible substrings of this length within the input.
For each substring, quickly count how many times that substring appears in the original input string.
If a substring appears at least twice, you've found a possible solution. Because we're checking from largest to smallest substrings, this is the longest possible substring. No need to check other substrings.
If you checked all substrings of a certain length and none appear twice, shorten the substring by one character and try again. Keep reducing the size until a match is found.
Repeat the process until a substring appears at least twice, or until you're checking single characters. If no substring ever appears twice, the result is an empty substring (or similar appropriate default result).
The first substring found that occurs at least twice is the longest substring that satisfies the condition. Return it.

Code Implementation

def find_maximum_length_substring_with_two_occurrences(input_string):
    string_length = len(input_string)
    for substring_length in range(string_length, 0, -1):
        for i in range(string_length - substring_length + 1):
            substring = input_string[i:i + substring_length]
            # Check if the substring appears at least twice
            if input_string.count(substring) >= 2:

                return substring
            
    return ""

Big(O) Analysis

Time Complexity

O(n^3) – The outer loop iterates from n-1 down to 1, representing the length of the substring to search for. The inner loop iterates through the string to extract substrings of the current length, which takes O(n) time. For each substring extracted, we need to check its occurrences in the original string which, in the worst case, can also take O(n) time. Therefore, the total time complexity is approximately O(n * n * n) which simplifies to O(n^3).

Space Complexity

O(1) – The algorithm primarily relies on iterating through substrings of the input string. The dominant space usage comes from counting substring occurrences within the original string. This count can be achieved without storing all occurrences, but rather by keeping a counter and indices, therefore the space remains constant regardless of the input string's length N. Thus, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return 0, indicating no substring exists since an empty string cannot contain any substrings.
String with only one character	Return 0, since a single character string cannot contain a substring that appears twice.
String where no substring appears twice	Return 0, signifying the absence of any valid substring appearing at least twice.
String with maximum allowed length (scalability)	Ensure the chosen algorithm (e.g., suffix tree or rolling hash) scales efficiently to avoid exceeding time limits.
String containing only one distinct character (e.g., 'aaaa')	Correctly identify the longest substring of repeated characters appearing twice, handling overlaps (e.g., 'aaa' in 'aaaa').
Overlapping occurrences of a long substring	The algorithm must correctly handle overlapping occurrences to identify the longest such substring.
Very long repeated substring near the beginning of the string	Ensure the algorithm doesn't prematurely terminate the search before finding the longest repeated substring.
Integer overflow when calculating hash values for long substrings (if using rolling hash)	Use modular arithmetic to prevent integer overflow when computing hash values.

Null or empty input string

How to Handle:

Return 0, indicating no substring exists since an empty string cannot contain any substrings.

String with only one character

How to Handle:

Return 0, since a single character string cannot contain a substring that appears twice.

String where no substring appears twice

How to Handle:

Return 0, signifying the absence of any valid substring appearing at least twice.

String with maximum allowed length (scalability)

How to Handle:

Ensure the chosen algorithm (e.g., suffix tree or rolling hash) scales efficiently to avoid exceeding time limits.

String containing only one distinct character (e.g., 'aaaa')

How to Handle:

Correctly identify the longest substring of repeated characters appearing twice, handling overlaps (e.g., 'aaa' in 'aaaa').

Overlapping occurrences of a long substring

How to Handle:

The algorithm must correctly handle overlapping occurrences to identify the *longest* such substring.

Very long repeated substring near the beginning of the string

How to Handle:

Ensure the algorithm doesn't prematurely terminate the search before finding the longest repeated substring.

Integer overflow when calculating hash values for long substrings (if using rolling hash)

How to Handle:

Use modular arithmetic to prevent integer overflow when computing hash values.

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`?
If no substring appears exactly twice, what should the function return?
Are overlapping occurrences of the substring allowed or disallowed?
Is the string `s` case-sensitive? In other words, should I consider "abc" and "Abc" as the same substring?
Can the input string `s` be empty or null?

Brute Force Solution

Approach

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

Start by picking a possible substring length, beginning with the longest possible length and working our way down to shorter ones.
For each length, generate every possible substring of that length from the original string.
For each substring, check how many times it appears in the original string.
If a substring appears at least two times, compare its length with the current longest substring found so far.
If the current substring is longer, update the longest substring found.
After checking all possible substrings and lengths, the last longest substring found is the answer.

Code Implementation

def find_maximum_length_substring_with_two_occurrences(text):
    maximum_length = 0
    result_substring = ""

    # Iterate through all possible substring lengths
    for substring_length in range(1, len(text) + 1):

        # Iterate through all possible starting positions for substrings
        for starting_index in range(len(text) - substring_length + 1):
            substring = text[starting_index:starting_index + substring_length]
            occurrence_count = 0

            # Count how many times the current substring appears in the text
            for i in range(len(text) - substring_length + 1):
                if text[i:i + substring_length] == substring:
                    occurrence_count += 1

            # Check if the substring appears exactly twice
            if occurrence_count == 2:

                # Update the longest substring if necessary
                if substring_length > maximum_length:
                    maximum_length = substring_length
                    result_substring = substring

    return result_substring

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Begin by assuming the entire input string could be our answer and progressively shorten it.
Start by looking for a substring that's just one character smaller than the entire input string. Try all possible substrings of this length within the input.
For each substring, quickly count how many times that substring appears in the original input string.
If a substring appears at least twice, you've found a possible solution. Because we're checking from largest to smallest substrings, this is the longest possible substring. No need to check other substrings.
If you checked all substrings of a certain length and none appear twice, shorten the substring by one character and try again. Keep reducing the size until a match is found.
Repeat the process until a substring appears at least twice, or until you're checking single characters. If no substring ever appears twice, the result is an empty substring (or similar appropriate default result).
The first substring found that occurs at least twice is the longest substring that satisfies the condition. Return it.

Code Implementation

def find_maximum_length_substring_with_two_occurrences(input_string):
    string_length = len(input_string)
    for substring_length in range(string_length, 0, -1):
        for i in range(string_length - substring_length + 1):
            substring = input_string[i:i + substring_length]
            # Check if the substring appears at least twice
            if input_string.count(substring) >= 2:

                return substring
            
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0, indicating no substring exists since an empty string cannot contain any substrings.
String with only one character	Return 0, since a single character string cannot contain a substring that appears twice.
String where no substring appears twice	Return 0, signifying the absence of any valid substring appearing at least twice.
String with maximum allowed length (scalability)	Ensure the chosen algorithm (e.g., suffix tree or rolling hash) scales efficiently to avoid exceeding time limits.
String containing only one distinct character (e.g., 'aaaa')	Correctly identify the longest substring of repeated characters appearing twice, handling overlaps (e.g., 'aaa' in 'aaaa').
Overlapping occurrences of a long substring	The algorithm must correctly handle overlapping occurrences to identify the longest such substring.
Very long repeated substring near the beginning of the string	Ensure the algorithm doesn't prematurely terminate the search before finding the longest repeated substring.
Integer overflow when calculating hash values for long substrings (if using rolling hash)	Use modular arithmetic to prevent integer overflow when computing hash values.

Null or empty input string

How to Handle:

Return 0, indicating no substring exists since an empty string cannot contain any substrings.

String with only one character

How to Handle:

Return 0, since a single character string cannot contain a substring that appears twice.

String where no substring appears twice

How to Handle:

Return 0, signifying the absence of any valid substring appearing at least twice.

String with maximum allowed length (scalability)

How to Handle:

Ensure the chosen algorithm (e.g., suffix tree or rolling hash) scales efficiently to avoid exceeding time limits.

String containing only one distinct character (e.g., 'aaaa')

How to Handle:

Correctly identify the longest substring of repeated characters appearing twice, handling overlaps (e.g., 'aaa' in 'aaaa').

Overlapping occurrences of a long substring

How to Handle:

The algorithm must correctly handle overlapping occurrences to identify the *longest* such substring.

Very long repeated substring near the beginning of the string

How to Handle:

Ensure the algorithm doesn't prematurely terminate the search before finding the longest repeated substring.

Integer overflow when calculating hash values for long substrings (if using rolling hash)

How to Handle:

Use modular arithmetic to prevent integer overflow when computing hash values.