最长子字符串的长度(二)【华为OD机试JAVA&Python&C++&JS题解】

标签：JAVA Python 题解 len 长子 int pattern 字符串长度

一. 题目-最长子字符串的长度(二)

给你一个字符串 s，字符串s首尾相连成一个环形，请你在环中找出’l’、‘o’、‘x’ 字符都恰好出现了偶数次最长子字符串的长度。
输入描述：
输入是一串小写的字母组成的字符串。
输出描述：
输出是一个整数
补充说明：
1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。

示例1

输入：

alolobo
输出：

6
说明：

最长子字符串之一是 “alolob”，它包含 ‘l’，'o’各 2 个，以及 0 个 ‘x’ 。

示例2

输入：

looxdolx
输出：

7
说明：

最长子字符串是 “oxdolxl”，由于是首尾连接在一起的，所以最后一个 ‘x’ 和开头的 'l’是连接在一起的，此字符串包含 2 个 ‘l’ ，2个 ‘o’ ，2个 ‘x’ 。

示例3

输入：

bcbcbc
输出：

6
说明：

这个示例中，字符串 “bcbcbc” 本身就是最长的，因为 ‘l’、‘o’、‘x’ 都出现了 0 次。

二.解题思路

为了找到符合条件的最长子字符串，我们可以使用滑动窗口的方法。首先，我们需要统计整个字符串中’l’、‘o’、'x’的出现次数。然后，我们可以使用两个指针，分别指向字符串的起始位置，并通过滑动窗口的方式遍历整个字符串。

在滑动窗口的过程中，我们需要维护一个计数器，记录当前窗口中’l’、‘o’、'x’出现的次数。如果当前窗口中这三个字符的出现次数都是偶数次，那么我们更新最长子字符串的长度。如果有一个字符的出现次数是奇数次，我们需要移动窗口的左指针，直到这个字符的出现次数也变为偶数次。

通过不断滑动窗口并更新最长子字符串的长度，最终我们就能找到符合条件的最长子字符串。

需要注意的是，由于字符串是环形的，我们在遍历过程中需要考虑首尾连接的情况。可以通过对字符串进行拼接，使其变成一个两倍长度的字符串，这样就可以处理环形的情况了。

具体步骤如下：

统计字符串中’l’、‘o’、'x’的出现次数。
将字符串拼接为两倍长度。
使用滑动窗口遍历字符串，维护一个计数器记录当前窗口中’l’、‘o’、'x’的出现次数。
如果当前窗口中这三个字符的出现次数都是偶数次，更新最长子字符串的长度。
如果有一个字符的出现次数是奇数次，移动窗口的左指针，直到这个字符的出现次数也变为偶数次。
最终得到最长子字符串的长度。

这样的算法复杂度是O(N)，其中N是字符串的长度。

三.题解代码

Python题解代码

def main():
    input_str = input()
    
    print(find_the_longest_substring(input_str + input_str))
 
def find_the_longest_substring(ss):
    s = list(ss)
    dp = [[0] * (len(s) + 1) for _ in range(8)]
    index = [[0, 0] for _ in range(8)]
    
    pattern = 0
    res = 0
    
    for i in range(len(s)):
        if s[i] == 'l':
            pattern ^= (1 << 0)
        elif s[i] == 'o':
            pattern ^= (1 << 1)
        elif s[i] == 'x':
            pattern ^= (1 << 2)
        
        dp[pattern][index[pattern][1]] = i
        index[pattern][1] += 1
        
        while True:
            if dp[pattern][index[pattern][1] - 1] - dp[pattern][index[pattern][0]] <= len(s) / 2:
                break
            index[pattern][0] += 1
        
        if res < dp[pattern][index[pattern][1] - 1] - dp[pattern][index[pattern][0]]:
            res = dp[pattern][index[pattern][1] - 1] - dp[pattern][index[pattern][0]]
    
    return res
 
if __name__ == "__main__":
    main()

JAVA题解代码

import java.util.Scanner;
import java.util.*;
import java.util.stream.Stream;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
 
public class Main { 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input_str = in.nextLine();
        
        System.out.println(findTheLongestSubstring(input_str + input_str));
    }
    
    public static int findTheLongestSubstring(String ss){
        char[] s = ss.toCharArray();
        int[][] dp = new int[8][s.length+1];
        int[][] index = new int[8][2];
        for (int i=0;i<8;i++){
            index[i][0] = 0;
            index[i][1] = 0;
        }
        dp[0][index[0][0]] = -1;
        index[0][1] += 1;
        int pattern = 0;
        int res = 0;
        for (int i=0;i<s.length;i++){
            if (s[i] == 'l'){
                pattern^= (1<<0);
            }else if (s[i] == 'o'){
                pattern^= (1<<1);
            }else if (s[i] == 'x'){
                pattern^= (1<<2);
            }
            dp[pattern][index[pattern][1]] = i;
            index[pattern][1] += 1;
            //长度不能超过n
            while(true){
                if (dp[pattern][index[pattern][1]-1] - dp[pattern][index[pattern][0]] <= s.length/2) {
                    break;
                }
                index[pattern][0] += 1;
            }
            if(res < dp[pattern][index[pattern][1]-1] - dp[pattern][index[pattern][0]]){
                res = dp[pattern][index[pattern][1]-1] - dp[pattern][index[pattern][0]];
            }
        }
        return res;
    }
    
    
    public static int[] split(String input_str,String chars){
        String[] tmp2 = input_str.split(chars);
        int[] counts = new int[tmp2.length];
        for (int i = 0; i < tmp2.length; i++) {  
            counts[i] = Integer.parseInt(tmp2[i]);
        }
        return counts;
    }
    
}

C/C++题解代码

#include <iostream>
#include <string>
using namespace std;
 
int main() {
  string in;
 
  cin >> in;
 
  size_t len = in.length();
 
 
  int res = 0;
 
  if (len == 1) {
 
    if (in[0] != 'l' && in[0] != 'o' && in[0] != 'x')
      cout << 1 << endl;
    else
      cout << 0 << endl;
    return 0;
  }
 
  {
    int i;
    for (i = 0; i < len; i++) {
      if (in[i] == 'l' || in[i] == 'o' || in[i] == 'x') {
        break;
      }
    }
    if (i == len) {
      cout << len << endl;
      return 0;
    }
  }
 
  int max_len_alllll = 0;
  for (int i = 0; i < len; i++) {
 
    int n_l = 0;
    int n_o = 0;
    int n_x = 0;
 
    int max_len_start_from_i = 0;
    for (int j = i; j < (i + len); j++) {
 
      int j_mod = j;
      if (j_mod >= len) {
        j_mod = j_mod % len;
      }
      int curr_char = in[j_mod];
 
      if (curr_char == 'l')
        n_l += 1;
      if (curr_char == 'o')
        n_o += 1;
      if (curr_char == 'x')
        n_x += 1;
 
      if (n_l % 2 == 0 && n_o % 2 == 0 && n_x % 2 == 0) {
        int curr_len = j - i + 1;
        if (curr_len > max_len_start_from_i)
          max_len_start_from_i = curr_len;
      }
    }
 
    if (max_len_start_from_i > max_len_alllll)
      max_len_alllll = max_len_start_from_i;
 
   
  }
 
  cout << max_len_alllll << endl;
 
  return 0;
}

JS题解代码

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (s) => {
    let n = s.length;
    s += s;
    let pre = [];
    for (let i = 0; i < (1 << 3); i++) pre.push([]);
    pre[0].push(-1);
    let x = 0, ans = 0;
    for (let i = 0; i < 2 * n; i++) {
        if (s[i] == 'l') x ^= 1;
        else if (s[i] == 'o') x ^= 2;
        else if (s[i] == 'x') x ^= 4;
        let q = pre[x];
        q.push(i);
        while (q[q.length - 1] - q[0] > n) q.shift();
        ans = Math.max(ans, i - q[0]);
    }
    console.log(ans);
    rl.close();
});

四.代码讲解(Java&Python&C++&JS分别讲解)

Python题解代码解析：

主函数 (main()):
- 从输入中读取字符串。
- 将输入字符串翻倍后传递给 find_the_longest_substring 函数。
- 输出 find_the_longest_substring 函数的结果。
子函数 (find_the_longest_substring(ss)) 解析:
- ss 是输入字符串的两倍长度。
- 将 ss 转换为列表 s。
- 使用动态规划，维护一个二维数组 dp 和一个二维数组 index，用于记录不同状态下字符 ‘l’、‘o’、‘x’ 最后出现的位置和区间起始位置。
- 使用异或操作构建状态 pattern，表示当前字符 ‘l’、‘o’、‘x’ 出现次数的奇偶性。
- 遍历字符串，更新状态、位置信息，同时维护最长子字符串的长度 res。
- 返回最终的最长子字符串长度。

JAVA题解代码解析：

主函数 (main()) 解析:
- 使用 Scanner 从标准输入中读取字符串。
- 将输入字符串翻倍后传递给 findTheLongestSubstring 方法。
- 输出 findTheLongestSubstring 方法的结果。
子函数 (findTheLongestSubstring(String ss)) 解析:
- 将输入字符串 ss 转换为字符数组 s。
- 使用动态规划，维护一个二维数组 dp 和一个二维数组 index，用于记录不同状态下字符 ‘l’、‘o’、‘x’ 最后出现的位置和区间起始位置。
- 使用异或操作构建状态 pattern，表示当前字符 ‘l’、‘o’、‘x’ 出现次数的奇偶性。
- 遍历字符数组，更新状态、位置信息，同时维护最长子字符串的长度 res。
- 返回最终的最长子字符串长度。

C/C++题解代码解析：

主函数 (main()) 解析:
- 从标准输入读取字符串。
- 计算字符串的长度。
- 若字符串长度为1，根据字符类型输出相应结果；否则，继续计算最长子字符串长度。
- 输出最终的最长子字符串长度。
最长子字符串计算部分解析:
- 使用两个嵌套循环遍历字符串，分别作为子字符串的起始和结束位置。
- 在内循环中，通过异或操作维护字符 ‘l’、‘o’、‘x’ 的出现次数奇偶性，并计算当前子字符串的长度。
- 若当前子字符串中这三个字符出现次数均为偶数次，则更新最长子字符串长度。
- 输出最终的最长子字符串长度。

JS题解代码解析：

主函数部分解析:
- 使用 readline 模块创建接口，等待用户输入字符串。
- 通过异或操作维护字符 ‘l’、‘o’、‘x’ 的出现次数奇偶性，并计算最长子字符串长度。
- 输出最终的最长子字符串长度。
最长子字符串计算部分解析:
- 使用异或操作构建状态 x，表示当前字符 ‘l’、‘o’、‘x’ 出现次数的奇偶性。
- 通过循环遍历字符串的两倍长度，更新状态、位置信息，同时维护最长子字符串的长度 ans。
- 输出最终的最长子字符串长度。

这些代码都采用了类似的思路，通过状态转移和动态规划的方式在字符串中寻找符合条件的最长子字符串。

寄语

标签：JAVA,Python,题解,len,长子,int,pattern,字符串,长度
From： https://blog.csdn.net/mrdeam/article/details/136986792