题目描述

给定一个字符串 $s$，该字符串首尾相连成环。我们需要找出环中包含偶数个字符 'o' 的最长子字符串的长度。

解题思路

为了找出包含偶数个 'o' 的最长子字符串，我们可以利用前缀和的概念和特定的数学技巧。我们会用一个变量来计数字符串中字符 'o' 的出现次数。

思路简述：

1. 奇偶讨论：

• 如果整个字符串中 'o' 的数量为偶数，则整个字符串都是答案，因为首尾相连后，整个环中 'o' 的数量仍然为偶数。
• 如果整个字符串中 'o' 的数量为奇数，那么只需删除字符串里的一个'o'，剩余的字符串就是最大长度的合法字符串。

2. 时间复杂度：由于我们最多遍历字符串两次（一次确定 'o' 的总数量，一次寻找最大有效长度），因此整个算法的时间复杂度为 $O(n)$，这是可行的。

代码实现

Python 代码实现

def max_length_even_o(s):
    n = len(s)
    count_o = s.count('o')
    
    # 如果'o'的数量为偶数，整个字符串都是答案
    if count_o % 2 == 0:
        return n
    # 'o'的数量为奇数，移除任意一个'o'
    else:
        return n-1

# 示例
s = input().strip()
print(max_length_even_o(s))

Java 代码实现

import java.util.Scanner;
public class Main {
    public static int maxLengthEvenO(String s) {
        int n = s.length();
        int countO = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'o') {
                countO++;
            }
        }
        
        // 如果'o'的数量为偶数，整个字符串都是答案
        if (countO % 2 == 0) {
            return n;
        }
        // 'o'的数量为奇数，移除任意一个'o'
        else{
            return n-1;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine().trim();
        System.out.println(maxLengthEvenO(s));  
    }
}

C++ 代码实现

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

int maxLengthEvenO(string s) {
    int n = s.length();
    int countO = 0;
    for (char c : s) {
        if (c == 'o') {
            countO++;
        }
    }
    
    // 如果'o'的数量为偶数，整个字符串都是答案
    if (countO % 2 == 0) {
        return n;
    }
    // 'o'的数量为奇数，移除任意一个'o'
    else{
        return n-1;
    }
}

int main() {
    string s;
    getline(cin, s);
    cout << maxLengthEvenO(s) << endl;  
    return 0;
}

题目描述

给你一个字符串 $s$ ，首尾相连成一个环形，请你再环中找出 '$o$' 字符出现了偶数次最长字符串的长度

输入描述

输入为一个小写字母组成的字符串。($1 \le s.length \le 5 × 10^5$)

输出描述

输出是一个整数。

样例1

输入

alolobo

输出

6

说明：最长字符串之一是"$alolob$"，它包含 $2$ 个'$o$'。

样例2

输入

looxdolx

输出

7

说明：最长字符串"oxdolxl"，由于是首尾连接一起的，所以最后一个 '$x$'和开头的 '$l$'是连接在一起的，此字符串包含 $2$ 个' $o$'。

样例3

输入

bcbcbc

输出

6

说明：这个示例中，字符串 "$bcbcbc$" 本身就是最长的，因为 '$o$' 都出现了 $0$ 次.