2022-12-24：给定一个字符串 s，其中都是英文小写字母，如果 s 中的子串含有的每种字符都是偶数个，那么这样的子串就是达标子串，子串要求是连续串。返回 s 中达标子串的最大长度。 1 ＜= s 的长

2022-12-24
北京
本文字数：1647 字
阅读完需：约 5 分钟

2022-12-24：给定一个字符串 s，其中都是英文小写字母，如果 s 中的子串含有的每种字符都是偶数个，那么这样的子串就是达标子串，子串要求是连续串。返回 s 中达标子串的最大长度。1 <= s 的长度 <= 10^5，字符种类都是英文小写。来自微软。

答案 2022-12-24：

shell 编写的代码真慢。map 存 status 最早状态的序号+status 整型存 26 个字母的状态。注意还没遍历的时候 map[0]=-1，这是最早的状态。时间复杂度：O(N)。空间复杂度：O(N)。

代码用 shell 编写。代码如下：

#!/bin/bash
# public static int getMax(int a, int b)function getMax(){    if [ $1 -gt $2 ];then        echo $1    else        echo $2    fi}
# public static boolean ok(String s, int l, int r)function ok(){    eval s=\$$1    local l=$2    local r=$3    if [ $[($r-$l+1)&1] == 1 ]     then         return 0    fi
    local cnts=()    local i=0    while [ $i -lt 26 ]    do        cnts[$i]=0        i=$[$i+1]    done
    i=$l    while [ $i -le $r ]    do        local c=${s:$i:1}        local num=$(echo $c| tr -d "\n" | od -An -t dC)        num=$[$num-97]        cnts[$num]=$[${cnts[$num]}+1]        i=$[$i+1]    done
    i=0    while [ $i -lt 26 ]    do        if [ $[${cnts[$i]}&1] == 1 ]         then             return 0        fi        i=$[$i+1]    done
    return 1}
# public static int maxLen1(String s)function maxLen1(){    eval s=\$$1    local n=${#s}    local ans=0    local i=0    while [ $i -lt $n ]    do        local j=$[$n-1]        while [ $j -ge $i ]        do            ok s $i $j            if [ $? == 1 ]             then                 ans=$(getMax $ans $[$j-$i+1])            fi            j=$[$j-1]        done        i=$[$i+1]    done
    echo $ans}
# public static int maxLen2(String s)function maxLen2(){    eval s=\$$1    local n=${#s}    declare -A map    map[0]=-1    local status=0    local ans=0    local i=0    while [ $i -lt $n ]    do        local c=${s:$i:1}        local num=$(echo $c| tr -d "\n" | od -An -t dC)        num=$[$num-97]        num=$[1<<$num]        status=$[($status)^($num)]        if [ "${map[$status]}" = "" ]         then             map[$status]=$i        else            ans=$(getMax $ans $[$i-${map[$status]}])        fi        i=$[$i+1]    done
    echo $ans}
# 为了测试# public static String randomString(int n, int v) function randomString(){    local n=$1    local v=$2    local i=0    local ans=""    while [ $i -lt $n ]    do        local temp=$RANDOM%$v        temp=$[$temp+97]        local a=$(echo $temp | awk '{printf("%c", $1)}')        ans=$ans$a        i=$[$i+1]    done    echo $ans}
# 为了测试function main(){    local s="moonfdd"    echo $(maxLen1 s)    echo $(maxLen2 s)
    local n=6    local v=6    local testTimes=5    printf "测试开始\r\n"    local i=0    while [ $i -lt $testTimes ]    do        printf "i = %d\r\n" $i        local s=$(randomString $n $v)        printf "s = %s\r\n" $s        local ans1=$(maxLen1 s)        local ans2=$(maxLen2 s)        if [ $ans1 != $ans2 ]         then             printf "%s\r\n" s            printf "%s\r\n" ans1            printf "%s\r\n" ans2            break        fi        printf "ans = %s\r\n" $ans1        printf "end===============\r\n"         i=$[$i+1]    done    printf "测试结束\r\n"    }
main maxLen1