(新卷,200分)- 最长子字符串的长度(二)（Java JS Python C）

(新卷,200分)- 最长子字符串的长度(二)（Java & JS & Python & C）

题目描述

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

输入描述

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

输出描述

输出是一个整数

备注

• 1 ≤ s.length ≤ 5 * 10^5
• s 只包含小写英文字母

用例

题目解析

本题其实就是

看本题前需要先把上面题目搞懂，否则本题解法看不懂。

本题与上面题目的区别在于，本题的主串s是环，即当遍历到s串尾部时，可以继续环动到s串头部。

如下图所示

上图中（黑色）部分是不可使用的，（绿色+黄色）的部分总是对应一个完整的字符串s。

本题如果继续按照前面leetcode那题的思路解题，则会发现使用哈希表时，不能只单单记录某个状态的最早出现位置。

而是需要记录某个状态的出现的所有位置（需要按照先后顺序依次记录）。

因为，本题随着绕环运动，黑色部分会逐渐侵蚀掉一些位置，而这些被侵蚀的位置，可能就是某个状态最早出现的位置，当该位置被侵蚀后，我们需要更新对应状态到新的最早出现位置。

如果使用队列记录某个状态出现的所有位置（按照先后顺序依次记录），那么队列头部记录的就是该状态的最早出现位置，如果该位置被侵蚀，那么我们就弹出队头，使用新的队头元素作为对应状态的最早出现位置。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { const s = await readline(); console.log(getResult(s)); })(); function getResult(s) { let status = 0b000; // map[i] 用于记录 状态i 出现的过的所有位置 const map = new Array(8).fill(0).map(() => []); map[0].push(-1); let maxLen = 0; for (let i = 0; i < s.length * 2; i++) { // 第二轮时，i>=s.length，此时i需要对s.length求余，避免后面越界 const c = s[i % s.length]; switch (c) { case "l": status ^= 0b100; break; case "o": status ^= 0b010; break; case "x": status ^= 0b001; break; } if (i < s.length) { // 第一轮时，i ∈ [0, s.length()), 左闭右开 // 记录该状态出现过的所有位置 map[status].push(i); } while (map[status].length > 0) { // status状态最早出现的位置 const earliest = map[status][0]; // i 是当前位置，和 earliest 位置的状态相同 if (i - earliest > s.length) { // 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliest map[status].shift(); } else { // 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度 maxLen = Math.max(maxLen, i - earliest); break; } } } return maxLen; }

Java算法源码

import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); System.out.println(getResult(s)); } public static int getResult(String s) { int status = 0b000; // map.get(i) 用于记录 状态i 出现的过的所有位置 ArrayList<LinkedList<Integer>> map = new ArrayList<>(); for (int i = 0; i < 8; i++) { map.add(new LinkedList<>()); } map.get(0).add(-1); int maxLen = 0; for (int i = 0; i < s.length() * 2; i++) { // 第二轮时，i>=s.length()，此时i需要对s.length()求余，避免后面越界 char c = s.charAt(i % s.length()); switch (c) { case 'l': status ^= 0b100; break; case 'o': status ^= 0b010; break; case 'x': status ^= 0b001; break; } if (i < s.length()) { // 第一轮时，i ∈ [0, s.length()), 左闭右开 // 记录该状态出现过的所有位置 map.get(status).add(i); } while (map.get(status).size() > 0) { // status状态最早出现的位置 int earliest = map.get(status).getFirst(); // i 是当前位置，和 earliest 位置的状态相同 if (i - earliest > s.length()) { // 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliest map.get(status).removeFirst(); } else { // 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度 maxLen = Math.max(maxLen, i - earliest); break; } } } return maxLen; } }

Python算法源码

# 输入获取 s = input() # 算法入口 def getResult(): status = 0b000 # dic[i] 用于记录 状态i 出现的过的所有位置 dic = [[] for _ in range(8)] dic[0].append(-1) maxLen = 0 for i in range(2 * len(s)): # 第二轮时，i>=s.length，此时i需要对s.length求余，避免后面越界 c = s[i % len(s)] if c == 'l': status ^= 0b100 elif c == 'o': status ^= 0b010 elif c == 'x': status ^= 0b001 if i < len(s): # 第一轮时，i ∈ [0, s.length()), 左闭右开 # 记录该状态出现过的所有位置 dic[status].append(i) while len(dic[status]) > 0: # status状态最早出现的位置 earliest = dic[status][0] # i 是当前位置，和 earliest 位置的状态相同 if i - earliest > len(s): # 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliest dic[status].pop(0) else: # 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度 maxLen = max(maxLen, i - earliest) break return maxLen # 算法调用 print(getResult())

C算法源码

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define MAX_SIZE 500000 char s[MAX_SIZE]; typedef struct ListNode { int ele; struct ListNode *next; } ListNode; typedef struct LinkedList { int size; ListNode *head; ListNode *tail; } LinkedList; LinkedList *new_LinkedList() { LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList)); link->size = 0; link->head = NULL; link->tail = NULL; return link; } void addLast_LinkedList(LinkedList *link, int ele) { ListNode *node = (ListNode *) malloc(sizeof(ListNode)); node->ele = ele; node->next = NULL; if (link->size == 0) { link->head = node; link->tail = node; } else { link->tail->next = node; link->tail = node; } link->size++; } int removeFirst_LinkedList(LinkedList *link) { if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) { link->head = NULL; link->tail = NULL; } else { link->head = link->head->next; } link->size--; int res = removed->ele; free(removed); return res; } int getResult() { int status = 0b000; // map[i] 用于记录 状态i 出现的过的所有位置 LinkedList *map[8]; for (int i = 0; i < 8; i++) { map[i] = new_LinkedList(); } addLast_LinkedList(map[0], -1); int maxLen = 0; int n = (int) strlen(s); for (int i = 0; i < n * 2; i++) { // 第二轮时，i>=s.length()，此时i需要对s.length()求余，避免后面越界 char c = s[i % n]; if (c == 'l') { status ^= 0b100; } else if (c == 'o') { status ^= 0b010; } else if (c == 'x') { status ^= 0b001; } if (i < n) { // 第一轮时，i ∈ [0, s.length()), 左闭右开 // 记录该状态出现过的所有位置 addLast_LinkedList(map[status], i); } while (map[status]->size > 0) { // status状态最早出现的位置 int earliest = map[status]->head->ele; // i 是当前位置，和 earliest 位置的状态相同 if (i - earliest > n) { // 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliest removeFirst_LinkedList(map[status]); } else { // 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度 maxLen = (int) fmax(maxLen, i - earliest); break; } } } return maxLen; } int main() { gets(s); printf("%d\n", getResult()); return 0; }