解题思路

这是一道关于字符串处理的题目，要找出最长的交错01子串。主要思路如下：

  1. 交错01串的定义：相邻位置的数字必须不同，即01交替出现
  2. 遍历字符串，统计每个位置开始的最长交错01串长度
  3. 对于每个位置 ：
    • 检查从 开始是否能形成交错01串
    • 如果可以，继续向后检查直到不满足条件
    • 更新最大长度
  4. 返回找到的最大长度

代码

#include <iostream>
#include <string>
using namespace std;

int findLongestAlternating(string& s) {
    int n = s.length();
    int maxLen = 1;
    
    for(int i = 0; i < n; i++) {
        int len = 1;
        // 从每个位置开始尝试
        for(int j = i; j < n-1; j++) {
            // 检查相邻位置是否不同
            if(s[j] != s[j+1]) {
                len++;
                maxLen = max(maxLen, len);
            } else {
                break;
            }
        }
    }
    
    return maxLen;
}

int main() {
    string s;
    cin >> s;
    cout << findLongestAlternating(s) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int findLongestAlternating(String s) {
        int n = s.length();
        int maxLen = 1;
        
        for(int i = 0; i < n; i++) {
            int len = 1;
            for(int j = i; j < n-1; j++) {
                if(s.charAt(j) != s.charAt(j+1)) {
                    len++;
                    maxLen = Math.max(maxLen, len);
                } else {
                    break;
                }
            }
        }
        
        return maxLen;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(findLongestAlternating(s));
    }
}

def find_longest_alternating(s):
    n = len(s)
    max_len = 1
    
    for i in range(n):
        length = 1
        for j in range(i, n-1):
            if s[j] != s[j+1]:
                length += 1
                max_len = max(max_len, length)
            else:
                break
                
    return max_len

if __name__ == "__main__":
    s = input().strip()
    print(find_longest_alternating(s))

算法及复杂度

  • 算法：双重循环遍历
  • 时间复杂度：，其中 是字符串长度
  • 空间复杂度：，只使用常数额外空间

优化思路：

  1. 可以使用动态规划优化，但对于这题的数据范围()，简单的双重循环已经足够
  2. 提前终止内层循环可以减少不必要的检查
  3. 如果找到长度为 的交错串，可以直接返回，因为这是可能的最大长度