#2981

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Longest Special Substring That Occurs Thrice I

Find the longest special substring in a string that appears at least three times, or return -1 if no such substring exists.

hash table string binary search sliding window counting

Problem Statement

You are given a string s consisting of lowercase English letters. Your goal is to find the length of the longest special substring within s that appears at least three times. A special substring consists of only a single character, like 'aaa' or 'bbb'. If no such substring exists, return -1.

A special substring is one that contains repeated occurrences of a single character. For example, 'aaa' is a valid special substring, while 'abc' is not. The challenge lies in identifying the longest special substring that appears at least three times, and optimizing the approach using binary search over the answer space.

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

Solution Approach

Binary Search for Optimal Length

The key to solving this problem efficiently is to apply binary search over the length of possible special substrings. By narrowing down the search space, we can test different lengths to find the longest one that satisfies the condition of appearing at least three times.

Hash Table for Counting Substring Occurrences

To track the frequency of each special substring, use a hash table. This allows for quick lookups and ensures that we can efficiently determine how many times a substring appears within the string.

Sliding Window for Substring Extraction

Use a sliding window approach to extract substrings of length k, where k is determined by binary search. This technique allows for checking all possible special substrings in the most efficient manner.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n^2)

The time complexity of this approach is O(n^2), where n is the length of the string, due to the sliding window mechanism and the binary search. Space complexity is also O(n^2) as the hash table stores all possible substrings and their counts.

What Interviewers Usually Probe

Candidate uses binary search to optimize substring length checking.
Candidate correctly applies a hash table to count substring occurrences efficiently.
Candidate demonstrates a clear understanding of sliding window techniques for substring extraction.

Common Pitfalls or Variants

Common pitfalls

Not properly handling edge cases where no valid special substring exists, leading to incorrect output.
Failure to optimize the search space with binary search, resulting in inefficient solutions.
Not correctly updating the count of substrings in the hash table, causing wrong results.

Follow-up variants

Consider strings with multiple possible special substrings of different lengths.
Optimize for larger inputs by adjusting the binary search space or improving hash table usage.
Explore solutions using different data structures to manage substring counts, such as arrays.

FAQ

What is the pattern used in 'Find Longest Special Substring That Occurs Thrice I'?

The primary pattern used is binary search over the valid answer space, optimizing substring length checking efficiently.

What should I do if no special substring occurs at least thrice?

Return -1 as there is no valid special substring that appears at least three times.

How do I optimize my solution for larger strings in this problem?

You can optimize the solution using binary search for substring length, reducing the search space and improving efficiency.

How do hash tables help in solving this problem?

Hash tables help by storing and quickly counting the occurrences of each special substring, enabling efficient checks during the sliding window step.

What is the time complexity of this approach?

The time complexity is O(n^2) due to the sliding window mechanism combined with binary search for optimal substring length.

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

Solution 2: Counting

The time complexity is $O(n)$

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

JavaScript

function maximumLength(s) {

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

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