题目描述

给你一个字符串 s，字符串的 能量 定义为：只包含一种字符的最长非空子字符串的长度。

请你返回字符串的能量。

样例

输入：s = "leetcode"
输出：2
解释：子字符串 "ee" 长度为 2 ，只包含字符 'e'。

输入：s = "abbcccddddeeeeedcba"
输出：5
解释：子字符串 "eeeee" 长度为 5 ，只包含字符 'e'。

输入：s = "triplepillooooow"
输出：5

输入：s = "hooraaaaaaaaaaay"
输出：11

输入：s = "tourist"
输出：1

限制

• 1 <= s.length <= 500
• s 只包含小写英文字母。

算法

(双指针) $O(n)$

1. 对于每个位置 i，求出尽可能小的位置 j，满足区间 [j, i] 中仅包含一种字符，此时可以用 i - j + 1 来更新答案。
2. 注意到 j 是随着 i 单调不减的，所以每次，我们可以让 s[j] 与 s[i] 比较，如果发现 s[j] != s[i]，则 j++。

时间复杂度

• 每个位置被遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int maxPower(string s) {
        int n = s.size();
        int ans = 0;
        for (int i = 0, j = 0; i < n; i++) {
            while (s[j] != s[i])
                j++;

            ans = max(ans, i - j + 1);
        }

        return ans;
    }
};