华为od（D卷） 环中最长子串/字符成环找偶数LOX

题目描述

给你一个字符串 s，字符串 s 首尾相连成一个环形，请你在环中找出 ‘l’、‘o’、‘x’ 字符都恰好出现了偶数次最长子字符串的长度。

输入描述

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

输出描述

输出是一个整数

1 ≤ s.length ≤ 5 * 10^5

s只包含小写英文字母

示例1

输入
alolobo

输出
6

示例2

输入
looxdolx

输出
7

示例3

输入
bcbcbc

输出
6

思路

1. 破环： 拼接字符串
2. 偶数判断：

状态标记：三位二进制分别记录LOX的出现次数， 1代表奇数次， 0代表偶数次，例如001代表l偶数次，o偶数次，x奇数次;
状态计算： “laaall” 索引为0时,状态100， 索引为5是状态也是100，5-0=5:相当于索引0-5的子串多一个l，子串字符串0-0的时候正好也多一个l，相减正好都是偶数，不多不少。

代码

public class Demo13 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String ss = s + s;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            String substring = ss.substring(i, i + s.length());
            max = Math.max(findLOXFromString(substring), max);
        }
        System.out.println(max);

        in.close();

    }
    public static int findLOXFromString(String s) {
        int res = 0;
        // key转态：字符出现位置二进制000  每一位代表字符出现的LOX是奇数还是偶数。奇数为1 偶数为0
        // value 第一次出现的位置
        Map<Byte, Integer> statusPos = new HashMap<>();
        statusPos.put((byte) 0, -1);
        Byte status = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case 'l':
                    status = (byte) (status ^ Byte.valueOf("001", 2));
                    break;
                case 'o':
                    status = (byte) (status ^ Byte.valueOf("010", 2));
                    break;
                case 'x':
                    status = (byte) (status ^ Byte.valueOf("100", 2));
                    break;
            }

            Integer sp = statusPos.getOrDefault(status, null);
            if (sp == null) {
                statusPos.put(status, i);
            } else {
                res = Math.max(res, i - sp);
            }
        }
        return res;

    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49