解题思路

这是一道字符串处理题目,主要思路如下:

  1. 特殊情况处理:

    • 长度为1:结果为0
    • 长度为2:如果两字符相同为0,不同为2
  2. 一般情况处理:

    • 从头部开始统计连续黑白相间的长度(headLen)
    • 从尾部开始统计连续黑白相间的长度(tailLen)
    • 统计中间部分的最长黑白相间长度
    • 如果首尾字符不同,可以考虑将头尾相连
  3. 最终结果为以上所有可能长度的最大值

代码

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

int main() {
    string s;
    while(cin >> s) {
        int len = s.length();
        
        // 特殊情况处理
        if(len == 1) {
            cout << "0" << endl;
            continue;
        }
        if(len == 2) {
            cout << (s[0] == s[1] ? "0" : "2") << endl;
            continue;
        }
        
        // 计算头部连续长度
        int headLen = 1, tailLen = 1;
        int start = 0, end = len - 1;
        
        for(; start < end; start++) {
            if(s[start] == s[start + 1]) break;
            headLen++;
        }
        
        // 如果扫描到结尾,说明整个串都是相间的
        if(start == end) {
            cout << headLen << endl;
            continue;
        }
        
        // 计算尾部连续长度
        for(; end > start; end--) {
            if(s[end] == s[end - 1]) break;
            tailLen++;
        }
        
        // 找出最大长度
        int maxLen = max(headLen, tailLen);
        int tempLen = 1;
        
        // 处理中间部分
        for(start++, end--; start < end; start++) {
            if(s[start] == s[start + 1]) {
                maxLen = max(maxLen, tempLen);
                tempLen = 1;
            } else {
                tempLen++;
            }
        }
        
        // 如果首尾字符不同,可以考虑连接
        if(s[0] != s[len - 1]) {
            maxLen = max(maxLen, headLen + tailLen);
        }
        
        cout << maxLen << endl;
    }
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String s = sc.next();
            int len = s.length();
            
            // 特殊情况处理
            if(len == 1) {
                System.out.println(0);
                continue;
            }
            if(len == 2) {
                System.out.println(s.charAt(0) == s.charAt(1) ? 0 : 2);
                continue;
            }
            
            // 计算头部连续长度
            int headLen = 1, tailLen = 1;
            int start = 0, end = len - 1;
            
            for(; start < end; start++) {
                if(s.charAt(start) == s.charAt(start + 1)) break;
                headLen++;
            }
            
            // 如果扫描到结尾,说明整个串都是相间的
            if(start == end) {
                System.out.println(headLen);
                continue;
            }
            
            // 计算尾部连续长度
            for(; end > start; end--) {
                if(s.charAt(end) == s.charAt(end - 1)) break;
                tailLen++;
            }
            
            // 找出最大长度
            int maxLen = Math.max(headLen, tailLen);
            int tempLen = 1;
            
            // 处理中间部分
            for(start++, end--; start < end; start++) {
                if(s.charAt(start) == s.charAt(start + 1)) {
                    maxLen = Math.max(maxLen, tempLen);
                    tempLen = 1;
                } else {
                    tempLen++;
                }
            }
            
            // 如果首尾字符不同,可以考虑连接
            if(s.charAt(0) != s.charAt(len - 1)) {
                maxLen = Math.max(maxLen, headLen + tailLen);
            }
            
            System.out.println(maxLen);
        }
    }
}
while True:
    try:
        s = input()
        length = len(s)
        
        # 特殊情况处理
        if length == 1:
            print(0)
            continue
        if length == 2:
            print(0 if s[0] == s[1] else 2)
            continue
            
        # 计算头部连续长度
        head_len = 1
        tail_len = 1
        start = 0
        end = length - 1
        
        while start < end:
            if s[start] == s[start + 1]:
                break
            head_len += 1
            start += 1
            
        # 如果扫描到结尾,说明整个串都是相间的
        if start == end:
            print(head_len)
            continue
            
        # 计算尾部连续长度
        while end > start:
            if s[end] == s[end - 1]:
                break
            tail_len += 1
            end -= 1
            
        # 找出最大长度
        max_len = max(head_len, tail_len)
        temp_len = 1
        
        # 处理中间部分
        start += 1
        end -= 1
        while start < end:
            if s[start] == s[start + 1]:
                max_len = max(max_len, temp_len)
                temp_len = 1
            else:
                temp_len += 1
            start += 1
            
        # 如果首尾字符不同,可以考虑连接
        if s[0] != s[-1]:
            max_len = max(max_len, head_len + tail_len)
            
        print(max_len)
        
    except EOFError:
        break

算法及复杂度

  • 算法:双指针 + 贪心
  • 时间复杂度: - 其中 为字符串长度,需要遍历一次字符串
  • 空间复杂度: - 只需要常数级别的额外空间存储计数器和指针