2982

2982. Find Longest Special Substring That Occurs Thrice II (Medium)

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

Companies: Google

Related Topics:
Hash Table, String, Binary Search, Sliding Window, Counting

Similar Questions:

• Longest Substring Without Repeating Characters (Medium)
• Longest Substring with At Least K Repeating Characters (Medium)

Hints:

• Let len[i] be the length of the longest special string ending with s[i].
• If i > 0 and s[i] == s[i - 1], len[i] = len[i - 1] + 1. Otherwise len[i] == 1.
• Group all the len[i] by s[i]. We have at most 26 groups.
• The maximum value of the third largest len[i] in each group is the answer.
• We only need to maintain the top three values for each group. You can use sorting, heap, or brute-force comparison to find the third largest value in each group.

Solution 1.

// OJ: https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-ii
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maximumLength(string s) {
        int N = s.size(), ans = -1;
        unordered_map<int, int> m[26] = {};
        for (int i = 0; i < N; ++i) {
            int len = 1, ch = s[i] - 'a';
            while (i + 1 < N && s[i + 1] == s[i]) ++i, ++len;
            if (len > 0) m[ch][len]++;
            if (len - 1 > 0) m[ch][len - 1] += 2;
            if (len - 2 > 0) m[ch][len - 2] += 3;
        }
        for (int ch = 0; ch < 26; ++ch) {
            for (auto &[len, cnt] : m[ch]) {
                if (cnt >= 3) ans = max(ans, len);
            }
        }
        return ans;
    }
};