首页 > 其他分享 >最长出现偶数次字符子串

最长出现偶数次字符子串

时间:2022-08-27 13:22:42浏览次数:54  
标签:子串 字符 前缀 int 偶数 出现

给定一个字符串求子串,使得子串中每个字符出现偶数次,例如

S = "baaadadd",满足条件的子串有 "aa", "adad", "aaadad",其中最长的是6,输出6

这道题一看会想使用滑动窗口解决,但是窗口大小是不能固定的,不能使用滑动窗口,因为一直往

窗口中添加字符串,无法判断什么时候窗口大小固定下来。

 

那另一种方法就是使用暴力解法,枚举每个子串,判断其中每个子串中的字符个数是否出现偶数个。

public class Solution {
    public static void main(String[] args) {
        String s = "baaadadd";

        int n = s.length();
        boolean breakFlag = false;
        int max = 0;
        // 枚举所有的长度
        for(int len = n; len > 0; len --){
            for(int j = 0; j <= (n - len); j++){
                if(satisfied(s, j, j + len)){
                    // [j, j + len) 区间的字符串满足条件,得到结果
                    max = len;
                    breakFlag = true;
                    break;
                }
            }
            if(breakFlag){
                break;
            }
        }
        System.out.println(max);
    }

    private static boolean satisfied(String s, int start, int end) {
        // 统计s[start, end) 区间字符串是否满足要求

        int[] hash = new int[26];

        for(int i = start; i < end; i++){
            char c = s.charAt(i);
            hash[c - 'a'] ++;
        }
        boolean satisfied = true;
        for(int i = 0; i < 26; i++){
            if(hash[i] % 2 != 0){
                satisfied = false;
                break;
            }
        }
        return satisfied;
    }
} 

此时时间复杂度为O(n^3)

 

但是这种方法复杂度太高了,每次统计子串都要计算一下子串中出现的元素的次数,可以使用前缀数组计算每个元素出现次数的累积和,那么在计算区间出现元素次数的时候,

就可以直接使用前缀数组末位下标,减去开始下标

例如:abbca,前缀数组样式[{a: 1},{a: 1, b: 1}, {a: 1, b: 2}, {a: 1, b: 2, c: 1}, {a: 2, b: 2, c: 1}]

那么使用前缀数组计算子串出现元素的次数的时候,可以不用遍历子串统计次数,直接利用前缀数组相减,

因此时间复杂度为O(n ^ 2)

 

那还有没有其他的优化方法吗,再优化的话一般是考虑O(nlogn)和O(n),O(nlogn)可以使用二分从左侧去考虑最大偶数字符子串,右侧考虑最大偶数字符子串,中间考虑,这个一般

大多数人停留在理论,代码实现确实很难。

 

其实还可以利用前缀思想,这里前缀不需要记录每个位置真正出现的次数,只需要记录每个字符出现是奇数次还是偶数次。

26个字符,使用26位表示每个字符出现奇偶情况。比如a, b , c 出现奇数次表示 00000000000000000000000111,1表示出现奇数次,0表示出现偶数次。

a, b , 出现奇数次,c出现偶数次,d出现奇数次表示00000000000000000000001011,其中这个可以用二进制移位,得到的数完全可以用int变量存其中的状态。

 根据 奇数 - 奇数 = 偶数,偶数 - 偶数 = 偶数

意思就是前缀列表中,如果存在此状态,那么当前状态到前缀列表中记录的那个下标长度就是满足条件的子串。

假设字符串为"caac",那么前缀表中分别存 100 —— 4,101 —— 5,100 —— 4,000  — 0 ,当判断到caa那个a字符串时,aa是满足要求的,发现没,能够在

前缀列表中找到相同的状态。

package com.ms_two;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        String s = "baaadadd";
        // 存放前缀状态以及下标
        Map<Integer, Integer> maps = new HashMap<>();
        // 0这个状态是存在的,让下标为-1
        maps.put(0, -1);
        int state = 0;
        int ans = 0;
        for(int i = 0; i < s.length(); i++){
            state ^= 1 << (s.charAt(i) - 'a');
            if(maps.containsKey(state)){
                ans = Math.max(ans, i - maps.get(state));
            }else{
                maps.put(state, i);
            }
        }
        System.out.println(ans);
    }
}

  

 

标签:子串,字符,前缀,int,偶数,出现
From: https://www.cnblogs.com/zzlback/p/16630391.html

相关文章

  • 给定一个字符串a 排成b 每次只能从原来的位置移动到队头 求操作多少次
    累加匹配的后缀因为只能往队头移动后缀相同就是不用移动的位置#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intn;strings1,s2;intmain(......
  • 字符串操作
    Golang//字符去重排序funclistDropDupSort(strstring)string{ //利用map去重 m:=make(map[rune]bool) for_,v:=rangestr{ m[v]=true } //追加到......
  • Js-字符串
    字符串字符串字符串也是一个数据结构,将同样的内容串在一块。因为在对应的js里面字符串属于一个值类型(值类型是常量常量是不能变)。字符串是不能改变的。结合数据结构里面......
  • LeetCode 1047. 删除字符串中的所有相邻重复项
    classSolution{public:stringremoveDuplicates(strings){stack<char>stack;for(inti=0;i<s.size();i++){if(stac......
  • C语言字符串处理函数 gets()和fgets()的区别及使用
    字符串函数(Stringprocessingfunction)也叫字符串处理函数,指的是编程语言中用来进行字符串处理的函数。本文主要介绍C语言中符串处理函数gets()和fgets()的区别使用方法,......
  • leetcode 205. Isomorphic Strings 同构字符串(简单)
    一、题目大意给定两个字符串s和t,判断它们是否是同构的。如果s中的字符可以按某种映射关系替换得到t,那么这两个字符串是同构的。每个出现的字符都应当映射到另一......
  • javascript怎么判断字符串是否是数字
    在javascript中,可以利用Number()函数和isNaN()函数来判断字符串是否是数字,语法“isNaN(Number("字符串",10)”;如果返回true,则该字符串不是数字,否则是数字。javascript判断......
  • Mysql 自定义随机字符串
    Mysql自定义随机字符串-搬砖工奶爸-博客园 https://www.cnblogs.com/--net/p/5784371.html 前几天在开发一个系统,需要用到随机字符串,但是mysql的库函数有没有直......
  • springboot:@RequestBody 注解只能处理json格式的请求字符串吗?
    原来@RequestBody注解常用来处理content-type是application/json编码的内容,而不能用来处理application/x-www-form-urlcoded编码的内容。参考:https://blog.csdn.n......
  • 字符串题目
    KMP#include<iostream>#include<cstdio>#include<string>#include<cstring>usingnamespacestd;constintN=1e6+10;chara[N];//存字符串intne[N];//next数组......