2982.找出出现至少三次的最长特殊子字符串 II

【LetMeFly】2982.找出出现至少三次的最长特殊子字符串 II：计数O(n)

力扣题目链接：https://leetcode.cn/problems/find-longest-special-substring-that-occurs-thrice-ii/

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。

子字符串 是字符串中的一个连续 非空 字符序列。

 

示例 1：

输入：s = "aaaa"
输出：2
解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
可以证明最大长度是 2 。

示例 2：

输入：s = "abcdef"
输出：-1
解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。

示例 3：

输入：s = "abcaba"
输出：1
解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
可以证明最大长度是 1 。

 

提示：

• 3 <= s.length <= 5 * 105
• s 仅由小写英文字母组成。

解题方法：计数

解题思路

“特殊子字符串”只能包含一种字符，因此我们可以将26种英文字符分开考虑。下面以字符a为例：

假设字符串a分别连续出现了t1次、t2次、...次、tn次，那么答案应该是多少呢？

其实我们只需要关注出现次数最多的3次（假设为t1、t2、t3）：

方法一，3个最长字符串都在t1中：

假设$t1=5$，则“aaaaa”中可以获得3个长度为3的字符串：“aaaaa”、“aaaaa”、“aaaaa”。

长度为$n$的连续字符串中可以提取3个长为$n-2$的“特殊子字符串”。

方法二，2个最长字符串在t1中，1个最长字符串在t2中：

假设$t1=5$而$t2=4$，则“aaaaa”中可以获得2个长度为4的字符串：“aaaaa”、“aaaaa”、“aaaa”中可以获得1个长度为4的字符串：“aaaa”。

长度为$n_1$和$n_2$（$n_1\geq n_2$）的连续字符串中可以提取3个长为$\min(n_1-1, n_2)$的“特殊子字符串”。

方法三，1个最长字符串在t1中，1个最长字符串在t2中，1个最长字符串在t3中：

假设$t1=5$而$t2=5$且$t3=5$，则其中分别可以提取一个长度为$5$的字符串。

长度为$n_1$、$n_2$和$n_3$（$n_1\geq n_2\geq n_3$）的连续字符串中可以提取3个长为$\min(n_1, n_2, n_3)$的“特殊子字符串”。

具体方法

开辟26个“三元组”，用来记录26个字母“连续出现次数”的前3名。遍历一次字符串即可得到该数组。

针对每个“三元组”，解题思路的三种方法中，最大的那个即为该字母的“最长特殊子字符串”。

26个字母中最长的即为答案。

• 时间复杂度$O(n)$
• 空间复杂度$O(C)$，其中一共26种字符（$C=26$）

AC代码

C++

class Solution {
private:
    inline void add1times(int times[], int n) {
        if (n > times[2]) {
            times[2] = n;
            if (times[2] > times[1]) {
                swap(times[2], times[1]);
                if (times[1] > times[0]) {
                    swap(times[1], times[0]);
                }
            }
        }        
    }

    inline int getTimes(int times[]) {
        return max(
            min(times[0], min(times[1], times[2])),
            max(
                min(times[0] - 1, times[1]),
                times[0] - 2
            )
        );
    }
public:
    int maximumLength(string s) {
        int times[26][3] = {0};
        int from = 0;
        for (int i = 1; i <= s.size(); i++) {
            if (i == s.size() || s[i] != s[i - 1]) {
                add1times(times[s[i - 1] - 'a'], i - from);
                from = i;
            }
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans = max(ans, getTimes(times[i]));
        }
        return ans ? ans : -1;
    }
};

时间击败95.24%，空间击败96.03%。

Go

// package main

func add(times []int, n int) {
    if n > times[2] {
        times[2] = n
        if times[2] > times[1] {
            times[2], times[1] = times[1], times[2]
            if times[1] > times[0] {
                times[1], times[0] = times[0], times[1]
            }
        }
    }
}

func max2(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func max3(a int, b int, c int) int {
    return max2(a, max2(b, c))
}

func min2(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func min3(a int, b int, c int) int {
    return min2(a, min2(b, c))
}

func getTimes(times []int) int {
    return max3 (
        min3(times[0], times[1], times[2]),
        min2(times[0] - 1, times[1]),
        times[0] - 2,  // 此逗号不可省略
    )
}

func maximumLength(s string) int {
    times := make([][3]int, 26)
    from := 0
    for i := 1; i <= len(s); i++ {
        if i == len(s) || s[i] != s[i - 1] {
            add(times[s[i - 1] - 'a'][:], i - from)
            from = i
        }
    }
    ans := 0
    for i := 0; i < 26; i++ {
        ans = max2(ans, getTimes(times[i][:]))
    }
    if ans != 0 {
        return ans
    }
    return -1
}

时间击败100%，空间击败100%。

Java

class Solution {
    private void add(int[] times, int n) {
        if (n > times[2]) {
            times[2] = n;
            if (times[2] > times[1]) {
                times[2] = times[2] ^ times[1] ^ (times[1] = times[2]);
                if (times[1] > times[0]) {
                    times[1] = times[1] ^ times[0] ^ (times[0] = times[1]);
                }
            }
        }
    }

    private int getTimes(int[] times) {
        return Math.max(
            Math.min(times[0], Math.min(times[1], times[2])),
            Math.max(
                Math.min(times[0] - 1, times[1]),
                times[0] - 2
            )
        );
    }

    public int maximumLength(String s) {
        int[][] times = new int[26][3];
        int from = 0;
        for (int i = 1; i <= s.length(); i++) {
            if (i == s.length() || s.charAt(i) != s.charAt(i - 1)) {
                add(times[s.charAt(i - 1) - 'a'], i - from);
                from = i;
            }
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans = Math.max(ans, getTimes(times[i]));
        }
        return ans != 0 ? ans : -1;
    }
}

时间击败88.89%，空间击败44.44%。

Python

# from typing import List

class Solution:
    def add(self, times, n) -> None:
        if n > times[2]:
            times[2] = n
            if times[2] > times[1]:
                times[1], times[2] = times[2], times[1]
                if times[1] > times[0]:
                    times[0], times[1] = times[1], times[0]
    
    def getTimes(self, times) -> int:
        return max(
            min(times),
            min(times[0] - 1, times[1]),
            times[0] - 2
        )

    def maximumLength(self, s: str) -> int:
        times = [[0, 0, 0] for _ in range(26)]
        from_ = 0
        for i in range(1, len(s) + 1):
            if i == len(s) or s[i] != s[i - 1]:
                self.add(times[ord(s[i - 1]) - ord('a')], i - from_)
                from_ = i
        ans = 0
        for i in range(26):
            ans = max(ans, self.getTimes(times[i]))
        return ans if ans else -1

时间击败75.34%，空间击败100%。

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/139334864