华为OD机试真题 - 最长子字符串的长度

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputString = scanner.nextLine();
        System.out.println(findLongestSubstringWithoutRepetition(inputString));
    }

    /**
     * 计算输入字符串中不包含重复字符的最长子串的长度。
     * 使用位运算和链表数组来跟踪每个状态（字符组合）下的最早出现位置。
     *
     * @param input 输入字符串
     * @return 不包含重复字符的最长子串的长度
     */
    public static int findLongestSubstringWithoutRepetition(String input) {
        int status = 0; // 使用位运算表示当前字符组合的状态
        LinkedList<Integer>[] positionMap = new LinkedList[8]; // 映射每个状态到最早出现位置的链表
        for (int i = 0; i < 8; i++) {
            positionMap[i] = new LinkedList<>();
        }
        positionMap[0].add(-1); // 初始化空状态的位置为-1
        int maxLength = 0; // 记录最长子串的长度

        for (int i = 0; i < input.length() * 2; i++) {
            char c = input.charAt(i % input.length()); // 循环输入字符串以处理重叠子串
            switch (c) {
                case 'l':
                    status ^= 4; // 对应0b100
                    break;
                case 'o':
                    status ^= 2; // 对应0b010
                    break;
                case 'x':
                    status ^= 1; // 对应0b001
                    break;
            }

            if (i < input.length()) {
                positionMap[status].add(i); // 记录当前字符在当前状态下的位置
            }

            // 清理不再可能构成最长子串的状态位置
            while (!positionMap[status].isEmpty()) {
                int earliestPosition = positionMap[status].getFirst();
                if (i - earliestPosition > input.length()) {
                    positionMap[status].removeFirst();
                } else {
                    maxLength = Math.max(maxLength, i - earliestPosition);
                    break;
                }
            }
        }

        return maxLength;
    }