找到最长的半重复子字符串

You are given a 0-indexed string s that consists of digits from 0 to 9.

A string t is called a semi-repetitive if there is at most one consecutive pair of the same digits inside t. For example, 0010, 002020, 0123, 2002, and 54944 are semi-repetitive while 00101022, and 1101234883 are not.

Return the length of the longest semi-repetitive substring inside s.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

Input: s = "52233"
Output: 4
Explanation: The longest semi-repetitive substring is "5223", which starts at i = 0 and ends at j = 3. 

Example 2:

Input: s = "5494"
Output: 4
Explanation: s is a semi-reptitive string, so the answer is 4.

Example 3:

Input: s = "1111111"
Output: 2
Explanation: The longest semi-repetitive substring is "11", which starts at i = 0 and ends at j = 1.

 

Constraints:

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

/*
题目思路：
使用Java Stream的功能来解决这个问题。我们仍然可以使用滑动窗口的方法，但这次用Stream API来处理字符串和计算长度。
*/

import java.util.stream.IntStream;

public class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        return IntStream.range(0, s.length())
                .flatMap(i -> IntStream.range(i + 1, s.length() + 1)
                        .map(j -> s.substring(i, j)))
                .filter(sub -> isSemiRepetitive(sub))
                .map(String::length)
                .max()
                .orElse(0);
    }

    private boolean isSemiRepetitive(String s) {
        int count = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
            }
            if (count > 1) {
                return false;
            }
        }
        return true;
    }
}

题解采用了双指针（滑动窗口）的方法来找到最长的半重复子字符串。这里使用了两个指针left和right分别表示当前考虑的子字符串的开始和结束位置。变量same用于记录当前窗口内相邻字符相等的对数，pre用于记录最后一对相等字符的位置。遍历字符串s，当发现相邻字符相等时，same增加。如果same等于2（即存在两对相等的相邻字符），则计算当前的子字符串长度并尝试更新最大长度ans。然后调整left到上一对相等字符之后的位置，重新计算窗口。遍历结束后，需要比较一次以确保最后的窗口也被考虑进最大长度。

O(n)

O(1)