Leetcode-6425. 找到最长的半重复子字符串

题目描述

给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。

如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串是半重复的。

请你返回 s 中最长半重复子字符串的长度。

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

示例 1：

输入：s = "52233"
输出：4
解释：最长半重复子字符串是 "5223" ，子字符串从 i = 0 开始，在 j = 3 处结束。
示例 2：

输入：s = "5494"
输出：4
解释：s 就是一个半重复字符串，所以答案为 4 。
示例 3：

输入：s = "1111111"
输出：2
解释：最长半重复子字符串是 "11" ，子字符串从 i = 0 开始，在 j = 1 处结束。

提示：

1 <= s.length <= 50
'0' <= s[i] <= '9'

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring

解题思路

额外定义四个变量，分别代表前两次遇到的“相邻相等字符串”，如图所示。每次遇到一对新的“相邻相等字符串”整体记录的变量向后移动。不难发现，'i-1'位置和p1的位置这段字符串，就是当前已变量的字符串中，符合要求的字符串。如图第三行：12345667890 这是已遍历的最长的。继续遍历到如图第四行，有更长的。

对于初始值都全部设置为0。需要注意的是，当字符串遍历完成之后，再计算p1位置到末尾的字符串长度，因为这段也是符合要求的字符串。

解题代码

第一版：

#include<iostream>
using namespace std;
class Solution {
 public:
  int longestSemiRepetitiveSubstring(string s) {
    if (s.size() <= 2) {
      return s.size();
    }
    int max_len = 0;
    int count = 0;

    int pre1 = 0;
    int p1 = 0;
    int pre2 = 0;
    int p2 = 0;
    for (int i = 1; i < s.size(); i++) {
      if (s[i] == s[i - 1]) {
        count++;
        // max_len = max(i - 1 - p1+1,max_len);
        max_len = max(i - p1, max_len);
        pre1 = pre2;
        p1 = p2;
        pre2 = i - 1;
        p2 = i;
      }
    }
    if (count < 2) {
      return s.size();
    } else {
      return max(max_len, (int)s.size() - p1);
    }
  }
};

代码优化

#include<iostream>
using namespace std;
class Solution {
 public:
  int longestSemiRepetitiveSubstring(string s) {
    if (s.size() <= 2) {
      return s.size();
    }
    int max_len = 0;

    int p1 = 0;
    int p2 = 0;
    for (int i = 1; i < s.size(); i++) {
      if (s[i] == s[i - 1]) {
        max_len = max(i - p1, max_len);
        p1 = p2;
        p2 = i;
      }
    }
    return max(max_len, (int)s.size() - p1);
  }
};