最长子串

📃题目

给定一个字符串，找出包含最多2个不同字符的最长子串长度

示例 1：

输入：axyxxxxyyyxdddadayx
输出：10
解释：其中符合条件的最长子串是 xyxxxxyyyx，子串中只包含x和y两个不同字符

🤔思路

子串问题第一反应想到了动态规划，开始动规五部曲分析

1、确定dp数组以及下标含义

dp数组应该是几维呢？

设置一维的话，dp[i]中应该存放的是以下标i结尾符合要求的字符串长度，但是在判断字符串是否符合要求时，我们还需要额外的信息——该字符串中不同字符的个数

因此dp数组设置成为二维，即dp[i][j]，i与一维的定义相同，而j表示以下标i结尾，有j+1个不同字符。

2、确定递推公式

在递推过程中存在两种情况：

当前字符与前一个字符相等，即s[i]==s[i-1]

dp[i][0] = dp[i-1][0] + 1;
// 因为dp[i-1][1]>dp[i-1][0]，所以不用考虑dp[i-1][0]+1的情况
dp[i][1] = dp[i-1][1] + 1;

当前字符与前一个字符不相等，即s[i]≠s[i-1]

//只能有一个不同字符，那么只能是s[i]这一个了
dp[i][0] = 1;
dp[i][1] = dp[i-1][0] + 1;

dp[i][1]乍一看感觉没问题，但是运行的时候，它忽略了一种场景，即以i-1结尾有两个不同字符的字符串，其中一个字符与s[i]相同，那么这种情况应该是dp[i][1] = dp[i-1][1] + 1

那么如何去判断另外一个”不知道位置“的字符是否与s[i]相同呢

其实这个位置与dp[i-1][1]息息相关，可以通过i-dp[i-1][1]-1获得另一个字符的下标位置，因为[i-dp[i-1][1],i-1]这个区间内的都是相同字符

所以第二种情况的递推公式，代码如下：

//只能有一个不同字符，那么只能是s[i]这一个了
dp[i][0] = 1;
if (s[i] != s[i - dp[i - 1][0] - 1]) dp[i][1] = dp[i - 1][0] + 1;
else dp[i][1] = dp[i - 1][1] + 1;

3、dp数组如何初始化

数组需要初始化的是dp[0][0]和dp[0][1]，两个分别表示下标i字符结尾有1个不同字符和有2个不同字符的字符串长度，从实际结果上看长度都是1

4、确定遍历顺序

从递推公式上可以看出，dp[i]需要dp[i-1]计算，所以应该从上至下计算

5、举例推导公式

使用字符串前半部分axyxxxxy为例

dp[i][j]	0	1
0	1	1
1	1	2
2	1	2
3	1	3
4	2	4
5	3	5
6	4	6
7	1	7

最终遍历dp数组寻找最大值得到结果

代码如下：

#include <bits/stdc++.h>
using namespace std;
 
int main() {
 string s;
 cin >> s;
 vector<vector<int>> dp(s.size(), vector<int>(2, 0));
 dp[0][0] = 1;
 dp[0][1] = 1;
 for (int i = 1; i < s.size(); i++) {
  if (s[i] == s[i - 1]) {
   dp[i][0] = dp[i - 1][0] + 1;
   dp[i][1] = dp[i - 1][1] + 1;
  } else {
   dp[i][0] = 1;
   if (s[i] != s[i - dp[i - 1][0] - 1]) dp[i][1] = dp[i - 1][0] + 1;
   else dp[i][1] = dp[i - 1][1] + 1;
  }
  cout << dp[i][1] << endl;
 }
 int result = dp[0][1];
 for (int i = 1; i < s.size(); i++) {
  result = max(result, dp[i][1]);
 }
 cout << result;
 return 0;
}

🔚总结

本题属于动态规划类型的题目，只是在递推公式的细节上需要琢磨，通过dp[i-1][0]处理不同字符是否重合是题目的关键，否则会卡测试案例

虽然是基础算法的稍微改进，但是自己构想写出来并提交AC的时候，那种成就感让人还想再来一题