【LeetCode每日一题】【2021/12/1】1446. 连续字符

• 1446. 连续字符
• • 方法1：动态规划
  • 方法2：动态规划 + 滚动数组
  • 结语

LeetCode: 1446. 连续字符

简 单 color{#00AF9B}{简单} 简单

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

设dp[i]为以第i个字符为结尾时的最大有效串的长度。这样一来，到达第i个字符时，一共有2种情况：

• 如果当前字符等于前一个字符，则dp[i]=dp[i-1]+1
• 如果不等，则dp[i]=1，也就是重新开始计数

我们可以得到如下的状态转移方程：
d p [ i ] = ( s [ i ] = = s [ i − 1 ] ? ( d p [ i − 1 ] + 1 ) : 1 ) dp[i]=(s[i]==s[i-1]?(dp[i-1]+1):1) dp[i]=(s[i]==s[i−1]?(dp[i−1]+1):1)
dp数组的首项也为1，因为以第一个字符为结尾的串长只能是1。

最后寻找dp数组中的最大值即可。

#include 
#include 
using namespace std;
class Solution
{
public:
    int maxPower(string s)
    {
        const int n = s.length();
        int *dp = new int[n];

        dp[0] = 1;
        for (int i = 1; i < n; i++)
        {
            dp[i] = s[i] == s[i - 1] ? dp[i - 1] + 1 : 1;
        }
        return *max_element(dp, dp + n);
    }
};

复杂度分析

• 时间复杂度： O ( n ) O(n) O(n)

• 空间复杂度： O ( n ) O(n) O(n)

参考结果

Accepted
333/333 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 5.42 % of cpp submissions (7.1 MB)

方法1中的状态转移方程：
d p [ i ] = ( s [ i ] = = s [ i − 1 ] ? ( d p [ i − 1 ] + 1 ) : 1 ) dp[i]=(s[i]==s[i-1]?(dp[i-1]+1):1) dp[i]=(s[i]==s[i−1]?(dp[i−1]+1):1)
从方程中可以发现，dp[i]只和dp[i-1]有关，那么就说明我们只需要一个变量就可以完成交换，这样就可以省去空间复杂度为 O ( n ) O(n) O(n)的dp数组了。

#include 
using namespace std;
class Solution
{
public:
    int maxPower(string s)
    {
        const int n = s.length();
        int cnt = 1, ans = 1;

        for (int i = 1; i < n; i++)
        {
            cnt = s[i] == s[i - 1] ? cnt + 1 : 1;
            ans = max(ans, cnt);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度： O ( n ) O(n) O(n)

• 空间复杂度： O ( 1 ) O(1) O(1)。我们只需要常量空间来存储若干变量。

参考结果

Accepted
333/333 cases passed (4 ms)
Your runtime beats 79.78 % of cpp submissions
Your memory usage beats 99.64 % of cpp submissions (6.5 MB)

本题其实不是一道难题，方法2可能对于大家来说就是第一个想到的方法，而且大家可能也不会想到动态规划。但本文就是想告诉大家：简单的方法2中，其实是动态规划的思想。