刷题笔记合集🔗

环中最长子串-字符成环找偶数O

问题描述

K小姐有一个由小写字母组成的字符串 。他想把这个字符串首尾相连形成一个环，然后在环中找出包含偶数个字母 'o' 的最长子串的长度。你能帮助她解决这个问题吗？

输入格式

输入一行，包含一个由小写字母组成的字符串 。

输出格式

输出一个整数，表示环中包含偶数个字母 'o' 的最长子串的长度。

样例输入1

alolobo

样例输出1

6

样例输入2

ooooo

样例输出2

4

样例输入3

abcde

样例输出3

5

样例 解释说明

样例1	在字符串 "alolobo" 中，最长的满足条件的子串之一是 "alolob"，它包含 2 个 'o' 字符，长度为 6。
样例2	在字符串 "ooooo" 中，最长的满足条件的子串是 "oooo"，它包含 4 个 'o' 字符，长度为 4。
样例3	在字符串 "abcde" 中，整个字符串都不包含 'o'，因此整个字符串都满足条件，长度为 5。

数据范围

• 

题解

结论

这道题目的关键在于理解字符串首尾相连形成环的特性，以及如何处理偶数个 'o' 的要求。

1. 首先，需要统计整个字符串中 'o' 的数量。这很重要，因为它决定了我们的策略。
2. 如果 'o' 的数量是偶数，那么整个字符串就是一个有效的解。为什么？因为无论从哪里开始，只要包含整个字符串，'o' 的数量总是偶数。
3. 如果 'o' 的数量是奇数，就需要删除一个字符来使 'o' 的数量变成偶数。
   • 只需要删除一个 'o'，就可以使剩下的 'o' 数量变成偶数。
4. 删除一个字符后，最长的子串长度就是原字符串长度减一。
5. 特别注意，如果字符串中没有 'o'，那么整个字符串都是有效的。

参考代码

• Python

def solve(s):
    # 统计字符串中 'o' 的数量
    count_o = s.count('o')
    
    # 如果 'o' 的数量是偶数，整个字符串都是有效的
    if count_o % 2 == 0:
        return len(s)
    # 如果 'o' 的数量是奇数，需要删除一个字符
    else:
        return len(s) - 1

# 读取输入
s = input().strip()

# 输出结果
print(solve(s))

• C

#include <stdio.h>
#include <string.h>

int solve(char* s) {
    int len = strlen(s);
    int count_o = 0;
    
    // 统计字符串中 'o' 的数量
    for (int i = 0; i < len; i++) {
        if (s[i] == 'o') {
            count_o++;