[leetCode 丶每日随机] 2730. 找到最长的半重复子串

原题:
https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/description/

描述:

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

如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，"0010" 、"002020" 、"0123" 、"2002" 和 "54944" 是半重复字符串，而 "00101022" （相邻的相同数字对是 00 和 22）和 "1101234883" （相邻的相同数字对是 11 和 88）不是半重复字符串。

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

示例 1：

输入: s = "52233"

输出： 4

解释：

最长的半重复子字符串是 "5223"。整个字符串 "52233" 有两个相邻的相同数字对 22 和 33，但最多只能选取一个。

示例 2:

输入： s = "5494"

输出： 4

解释：

s 是一个半重复字符串。

示例 3：

输入： s = "1111111"

输出： 2

解释：

最长的半重复子字符串是 "11"。子字符串 "111" 有两个相邻的相同数字对，但最多允许选取一个。

提示

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

个人版答案


class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        String result = "";
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            StringBuilder temp = new StringBuilder(String.valueOf(charArray[i]));
            char next = charArray[i];
            boolean is = false;
            for (int j = i + 1; j < charArray.length; j++) {
                if (next != charArray[j]) {
                    temp.append(charArray[j]);
                    next = charArray[j];
                } else {
                    if (is) {
                        break;
                    } else {
                        is = true;
                        temp.append(charArray[j]);
                        next = charArray[j];
                    }
                }
            }
            if (temp.length() > result.length()) {
                result = temp.toString();
            }
        }
        if (!result.isEmpty()) {
            return result.length();
        }
        return 0;
    }
}

5ms 答案及进阶版**


class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        char []chars = s.toCharArray();
        int  same = 0;
        int ans = 1;
        int left = 0;
        int n = chars.length;

        for(int i = 1; i < n ; i++){
            if(chars[i] == chars[i - 1] && ++same > 1 ){
                for(left++; chars[left] != chars[left - 1]; left ++);
                same = 1;
            }
            ans = Math.max(ans,i + 1 -left);
        }
        return ans;
    }
}