华为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;}}