2024华为OD机试 - 最长子字符串的长度（一）JAVA

2024华为OD机试真题，代码包含语言java代码基本都有详细注释。

题目描述

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

输入描述

输入是一个小写字母组成的字符串

输出描述

输出是一个整数

备注

• 1 ≤ s.length ≤ 500000
• s 只包含小写英文字母

用例

声明

上述内容部分整理自考生的真实反馈以及网络资源的搜集，我们始终尊重原作者的权益。如若发现任何内容侵犯了您的版权，敬请及时与我们取得联系，我们将立即进行删除处理。

此外，本材料后续的解析与代码部分均为我方原创思考与分析，凝聚了我们的心血与智慧。我们恳请各位尊重原创，切勿随意搬运或抄袭，共同维护良好的学术与创作环境。谢谢！

订阅后可看完整内容，试看真题如下：

华为OD机试真题 - 剩余银饰的重量 (D卷,100分)

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

题目解析

为了找到环形字符串中'o'字符出现偶数次的最长子字符串的长度，我们可以采用滑动窗口（双指针）的方法。由于字符串是环形的，我们需要考虑首尾相连的情况。

1. 初始化：设置两个指针left和right，初始时都指向字符串s的起始位置。初始化一个计数器count来记录当前窗口内'o'字符的数量，初始值为0。初始化一个变量maxLength来记录最长子字符串的长度，初始值为0。
2. 扩展右指针：移动right指针，并更新count，即count += (s[right] == 'o')。当right指针到达字符串末尾时，由于字符串是环形的，我们需要将其重新指向字符串的起始位置，并继续移动。
3. 调整左指针：如果count变为奇数（即当前窗口内'o'字符的数量为奇数），我们需要移动left指针，并减少count，即count -= (s[left] == 'o')，直到count再次变为偶数。
4. 更新最长子字符串长度：在每次移动right指针后，如果count为偶数，则更新maxLength为当前窗口长度和maxLength的较大值，即maxLength = max(maxLength, right - left + 1)（注意，如果right指针已经重新指向了字符串的起始位置，则窗口长度应为len(s) - left + right + 1）。
5. 重复步骤2-4：重复上述步骤，直到right指针再次指向字符串的起始位置，并且left指针也指向了起始位置（即整个字符串都被遍历过）。
6. 返回结果：返回maxLength作为结果。

这种方法的时间复杂度为O(n)，其中n是字符串的长度，因为我们只遍历了字符串两次（一次是right指针从起始位置到末尾，另一次是right指针从末尾回到起始位置）。空间复杂度为O(1)，因为我们只使用了常数个额外变量。

注意：题目中要求的是'o'字符出现偶数次的最长子字符串，而不是特定次数（如n次）的最长子字符串。因此，在解题过程中，我们只需要关注'o'字符的奇偶性，而不需要设定一个具体的次数n

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.nextLine()));
  }

  public static int getResult(String s) {
    int n = s.length();
    int zeroCount = (int) s.chars().filter(ch -> ch == 'o').count();

    return zeroCount % 2 == 0 ? n : n - 1;
  }
}