#2982

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Longest Special Substring That Occurs Thrice II

Find the longest special substring that occurs at least three times in a given string using binary search and hash table techniques.

hash table string binary search sliding window counting

Problem Statement

You are given a string s consisting of lowercase English letters. A substring is called special if it is made up of only one character, such as "aaa" or "bb". You need to find the length of the longest special substring that occurs at least three times within the string. If no such substring exists, return -1.

For example, in the string "aaaa", the longest special substring is "aa", which appears three times. In a string like "abcdef", no special substring occurs at least three times, so the output is -1. You must solve this problem efficiently, considering the constraints.

Examples

Example 1

Input: s = "aaaa"

Output: 2

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

There exists no special substring which occurs at least thrice. Hence return -1.

Example 3

Input: s = "abcaba"

Output: 1

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 <= 5 * 105
s consists of only lowercase English letters.

Solution Approach

Binary Search Over Valid Answer Space

Start by applying binary search to find the longest possible length of a special substring that occurs at least three times. The idea is to binary search over the substring lengths, from 1 to the length of the string, and check for each length if there exists a special substring of that length occurring three or more times.

Hash Table for Occurrences

For each length during the binary search, use a hash table to track the frequency of special substrings of that length. If any special substring occurs three times, update the binary search bounds accordingly to narrow down the possible maximum length.

Sliding Window for Efficiency

To efficiently check each substring of a given length, employ a sliding window technique. This will allow you to slide through the string, extract substrings of the required length, and update the hash table in constant time.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(c \cdot k) \approx O(1)

The time complexity is O(n) due to the sliding window technique and hash table operations, where n is the length of the string. The space complexity is O(c * k), which is approximately O(1) since we only store a fixed number of substrings based on the input size and substring length.

What Interviewers Usually Probe

Can the candidate apply binary search effectively on the valid answer space?
Does the candidate optimize the substring check with hash tables and sliding windows?
How well does the candidate manage edge cases, such as strings without repeating substrings?

Common Pitfalls or Variants

Common pitfalls

Failing to handle edge cases where no special substring occurs three times.
Inefficiently checking all substrings without using binary search and hash tables.
Overcomplicating the solution with unnecessary algorithms or data structures.

Follow-up variants

What if the problem asked for substrings that occur at least twice instead of three times?
What if the substring could be made up of more than one character?
What if the input string contained uppercase letters or was case-insensitive?

FAQ

What is the primary pattern in this problem?

The primary pattern is binary search over the valid answer space to find the longest special substring that occurs at least three times.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the string. This is due to the sliding window technique and hash table usage.

How do you check if a special substring occurs three times?

You use a hash table to track the occurrences of each special substring and verify if any appears at least three times.

Why is binary search important in solving this problem?

Binary search helps efficiently narrow down the possible lengths for the longest special substring by checking feasible substring lengths within the search space.

What if no special substring occurs at least three times?

In this case, return -1 as specified in the problem statement.

terminal

Solution

Solution 1: Binary Search + Sliding Window Counting

We notice that if there exists a special substring of length $x$ that appears at least three times, then a special substring of length $x-1$ must also exist. This exhibits a monotonicity, so we can use binary search to find the longest special substring.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def maximumLength(self, s: str) -> int:
        def check(x: int) -> bool:
            cnt = defaultdict(int)
            i = 0
            while i < n:
                j = i + 1
                while j < n and s[j] == s[i]:
                    j += 1
                cnt[s[i]] += max(0, j - i - x + 1)
                i = j
            return max(cnt.values()) >= 3

        n = len(s)
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return -1 if l == 0 else l

Continue Practicing

#2981 find longest special substring that occurs thrice i #2953 count complete substrings #3016 minimum number of pushes to type word ii