Find Longest Special Substring That Occurs Thrice I

Medium

Asked by:

+1

More companies

19 views

Topics:

Strings

You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "aaaa"
Output: 2
Explanation: The longest special substring which occurs thrice is "aa": substrings "aaaa", "aaaa", and "aaaa".
It can be shown that the maximum length achievable is 2.

Example 2:

Input: s = "abcdef"
Output: -1
Explanation: There exists no special substring which occurs at least thrice. Hence return -1.

Example 3:

Input: s = "abcaba"
Output: 1
Explanation: The longest special substring which occurs thrice is "a": substrings "abcaba", "abcaba", and "abcaba".
It can be shown that the maximum length achievable is 1.

Constraints:

3 <= s.length <= 50
s consists of only lowercase English letters.

Try coding it in LeetCode

Find Longest Special Substring That Occurs Thrice I

Medium

Asked by:

19 views

Topics:

Strings

You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "aaaa"
Output: 2
Explanation: The longest special substring which occurs thrice is "aa": substrings "aaaa", "aaaa", and "aaaa".
It can be shown that the maximum length achievable is 2.

Example 2:

Input: s = "abcdef"
Output: -1
Explanation: There exists no special substring which occurs at least thrice. Hence return -1.

Example 3:

Input: s = "abcaba"
Output: 1
Explanation: The longest special substring which occurs thrice is "a": substrings "abcaba", "abcaba", and "abcaba".
It can be shown that the maximum length achievable is 1.

Constraints:

3 <= s.length <= 50
s consists of only 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 multiple special substrings of the same maximum length occur at least three times, should I return the length of any one of them, or is there a specific one I should prioritize?
Can the input string s be empty or null?
Is a single character considered a special substring? For example, if 'a' occurs three times, is that a valid special substring?
Are overlapping occurrences of the substring counted as distinct occurrences?

Brute Force Solution

Approach

The brute force approach to find the longest special substring appearing thrice involves checking every possible substring of the input string. We generate each substring, count how many times it appears in the original string, and keep track of the longest substring that appears at least three times. Ultimately we check *every* possibility.

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

Start by looking at substrings of length one. Check if each single character appears at least three times in the main string.
Next, consider all substrings of length two. Again, check how many times each of these two-character substrings appears in the main string.
Continue doing this for substrings of increasing lengths - length three, length four, and so on, up to the length of the entire main string.
For each substring length, examine every possible substring within the main string.
As you check each substring, count how many times it appears in the original string. Make sure the counts are correct.
While going through all substrings, keep track of the longest substring that you've found so far that appears at least three times.
After checking all possible substrings and their counts, the longest substring you've kept track of is the answer.

Code Implementation

def find_longest_special_substring_that_occurs_thrice_i(input_string):
    longest_substring_found = ""
    string_length = len(input_string)

    for substring_length in range(1, string_length + 1):
        for starting_index in range(string_length - substring_length + 1):
            substring = input_string[starting_index:starting_index + substring_length]
            substring_count = 0

            # Count the number of occurrences of the current substring
            for i in range(string_length - substring_length + 1):
                if input_string[i:i + substring_length] == substring:
                    substring_count += 1

            #Check if the substring occurs at least thrice
            if substring_count >= 3:

                # Update the longest substring if the current substring is longer
                if substring_length > len(longest_substring_found):

                    longest_substring_found = substring

    return longest_substring_found

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible substring lengths from 1 to n, where n is the length of the input string. For each substring length (let's call it 'len'), it iterates through all possible starting positions of substrings with that length. The number of possible substrings of length 'len' is n - len + 1, which is O(n). For each substring, it counts the number of times the substring appears in the original string, which takes O(n * len) time. Thus, the total time complexity is approximately the sum of (n - len + 1) * (n * len) for len from 1 to n. This simplifies to O(n^3) because we are iterating through substring lengths, starting positions, and then comparing the substring in a full string.

Space Complexity

O(1) – The provided approach primarily involves iterating through substrings and counting their occurrences within the input string. It appears the described algorithm only needs to store a few variables like substring length, current substring, and a count. The amount of extra space needed for these few scalar variables does not scale with the size N of the input string. Therefore, the space complexity is constant, or O(1).

Optimal Solution

Approach

The optimal approach is to check substrings of decreasing lengths to find the longest one that appears at least three times. We can do this efficiently by keeping track of the occurrences of substrings and stopping early once we find a valid one.

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

Start by considering the longest possible substring length.
Check if any substring of that length appears at least three times in the original string.
If a substring of that length is found, you've found the longest one and can stop.
If no substring of the current length appears three times, reduce the length and repeat the check.
Continue reducing the length until you find a substring that appears at least three times, or the length becomes zero.
If you find a substring appearing thrice, return it; otherwise, if you checked all possible lengths and found nothing, return an empty string.

Code Implementation

def find_longest_special_substring_that_occurs_thrice(input_string):
    string_length = len(input_string)

    for substring_length in range(string_length - 1, 0, -1):
        # Iterate through possible substring lengths
        for i in range(string_length - substring_length + 1):
            substring = input_string[i:i + substring_length]
            count = 0

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

            # If a substring appears thrice, return it
            if count >= 3:
                return substring

    # No substring appearing at least thrice found
    return ""

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through substring lengths from n down to 1. For each length l, it extracts all substrings of length l, which takes O(n) time since there are n-l+1 such substrings. For each substring, we need to check for its occurrences in the original string. This can be done in O(n) time by iterating through the string and comparing the substring. Since we iterate through substring lengths from n to 1 and perform O(n) operations for each length, the overall time complexity is approximately O(n * n), which simplifies to O(n^2). The substring comparisons dominate the cost.

Space Complexity

O(N^2) – The algorithm checks substrings of decreasing lengths, storing substring occurrences to find one appearing at least three times. A hash map (or similar data structure) is used to store these substring counts, and in the worst case, this map can potentially store all possible substrings of the input string. The number of possible substrings of a string of length N is O(N^2), leading to a space complexity of O(N^2) for storing the substring counts.

Edge Cases

Case	How to Handle
Empty string input	Return 0 immediately as there are no substrings to evaluate.
String with length less than 3	Return 0 since a substring must appear at least thrice, which is impossible with fewer than 3 characters.
String with only one distinct character that appears fewer than three times	Iterate through the string and count the occurrences; return 0 if the count is less than 3.
String with only one distinct character appearing many times (e.g., 'aaaaaaaaaa')	The solution should correctly identify the length of the string as the answer.
String with many different characters and no special substrings appearing three times	The solution should iterate through all possible special substrings and correctly return 0.
String with some special substrings appearing exactly twice	The solution must correctly ignore these substrings as it only needs to consider substrings appearing at least three times.
String with multiple special substrings of the same length, each appearing at least three times	The solution should return the length of any of these longest substrings since they are all valid maximums.
Very long string to check performance and avoid Time Limit Exceeded (TLE)	Optimize the search to efficiently count substring occurences; substring search needs to be efficient to avoid TLE for long strings.

Empty string input

How to Handle:

Return 0 immediately as there are no substrings to evaluate.

String with length less than 3

How to Handle:

Return 0 since a substring must appear at least thrice, which is impossible with fewer than 3 characters.

String with only one distinct character that appears fewer than three times

How to Handle:

Iterate through the string and count the occurrences; return 0 if the count is less than 3.

String with only one distinct character appearing many times (e.g., 'aaaaaaaaaa')

How to Handle:

The solution should correctly identify the length of the string as the answer.

String with many different characters and no special substrings appearing three times

How to Handle:

The solution should iterate through all possible special substrings and correctly return 0.

String with some special substrings appearing exactly twice

How to Handle:

The solution must correctly ignore these substrings as it only needs to consider substrings appearing at least three times.

String with multiple special substrings of the same length, each appearing at least three times

How to Handle:

The solution should return the length of any of these longest substrings since they are all valid maximums.

Very long string to check performance and avoid Time Limit Exceeded (TLE)

How to Handle:

Optimize the search to efficiently count substring occurences; substring search needs to be efficient to avoid TLE for long strings.