建设网站建站公司_网站建设合同的要素及签订注意事项_百度竞价效果怎么样_学软件开发学费多少钱

Description

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

Solution

Binary Search

So the possible result lies within [1, len(s) - 2], so we could use a binary search to solve this problem. Given a possible special substring length, we need to know its frequency. To solve this, use a sliding window. If the new element is not the same as the old element, then shrink the window to be size 1 at the new element. Otherwise expanding the window. If the length of the window is the special substring length, then we found one, use a hashmap to record its frequency, and shrink the window size by 1.

Time complexity: KaTeX parse error: Undefined control sequence: \logn at position 4: o(n\̲l̲o̲g̲n̲)
Space complexity: $o(n)$

Code

Binary Search

class Solution:def maximumLength(self, s: str) -> int:def substring_appear_atleast_thrice(substring_len: int) -> int:cnt = {}window_left = 0for window_right in range(len(s)):if s[window_right] != s[window_left]:window_left = window_rightif window_right - window_left + 1 == substring_len:substring = s[window_left: window_right + 1]window_left += 1cnt[substring] = cnt.get(substring, 0) + 1if cnt[substring] >= 3:return Truereturn Falseleft, right = 1, len(s) - 2while left < right:mid = (left + right + 1) >> 1if substring_appear_atleast_thrice(mid):left = midelse:right = mid - 1mid = (left + right + 1) >> 1if substring_appear_atleast_thrice(mid):return midelse:return -1