【微软笔试】找出字符串中最长各字母出现皆为偶数的子字符串

总结：连续子串状态前缀+动态哈希，不连续子串排列组合问题

子串是连续的

题目描述

写一个函数:def，对于给定一个由N个小写英文字母组成的字符串S，返回每个字母出现偶数次的最长子字符串的长度。子字符串被定义为字符串的连续段。如果不存在这样的子字符串，返回0。
关键考点：动态哈希+状态压缩

例子

例子:1. 给定S =“bdaaadadb”，函数应该返回6。每个字母出现偶数次的子字符串是"aa"， “adad”， “daaada"和"aaadad”。其中最长的是6。
2. 给定S = “abacb”，函数应该返回0。不存在每个字母出现偶数次的非空子字符串。3.给定S = 'zthtzh '，函数应该返回6。整个字符串中的每个字母出现的次数都是偶数。对以下假设写一个有效的算法，注：N为范围[1…100,000]内的整数，字符串S只包含小写字母(‘a’-'z)。

解题思路

类似于网易的笔试第二题：【秋招笔试复盘】秋招的第一场笔试——网易。

1. 使用前缀和来记录当前子字符串的统计情况，这里的一个技巧是动态哈希。如果我们只想遍历一遍，那么就必须保存一些状态。对于任意一个子字符串，可以看作是右边界的前缀和与左边界前缀和之差，于是我们在遍历的过程中不停地把当前下标计算得到的前缀和丢入到map中。这样任意一个子字符串都可以用当前前缀和 - map中已存前缀和来还原得到。
2. 另一个技巧是状态压缩。我们需要思考如何编码当前前缀和的一个状态，由题意可知我们并不需要关心具体的统计个数，仅需要知道奇偶性，而奇偶刚好可以可以对应01两种状态，字母的个数为26，于是我们可以用一个26位的二进制来编码当前字符串的统计状态。只要当前字符串的状态和map中已有的字符串的状态相同，那么我们就认为由这两个字符串之差构建的子字符串字母皆为偶数。
3. 第三个技巧是如何更新前缀和状态，这里用到了二进制的异或技巧。我们需要对当前下标字母对应的二进制位取反，其他位保持不变，这个需求可以由异或实现。
4. 最后要注意的是，map中的key是state，value是对应的下标。对于相同的state，为了使最后计算的子字符串尽可能长，我们都是保留最前面的那个下标，所以一旦map中已经有state了，我们就不去更新其下标。

def solution(s):
    state = 0
    statemap = {}
    statemap[0] = -1
    ans = 0
    for i in range(len(s)):
        ind = ord(s[i]) - ord('a')
        stack ^= (1 << ind)
        if state in statemap:
            ans = max(ans, i-statemap[state])
        else:
            statemap[state] = i
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

子串不连续

题目描述

定义字符串中每个字母出现的次数是偶数为好串，问对于一个字符串，有多少子序列是好串（子序列可以不连续）？

例子

"ababa"有"aa"4个，"bb"1个，"abab"1个，"abba"1个，"baba"1个

解题思路

统计字符串中的各字母数，然后排列组合算所有可能数。例如a有5个，那么可以选择4个a，2个啊，0个a，对应是C54+C52+C50的总可能数，其他字母也一样，然后相乘就行。
特别注意他和前面一题连续子串的区别，因为本题子串可以不连续，因此不能用前缀思想计算。硬做dp状态2^26太多了。实际上细想一下，不连续子串本质上就是排列组合问题。

from collections import Counter
from functools import reduce
import math
 
MOD = 10**9+7
strings = input()
scount = Counter(strings)
cntlist = [v for k, v in scount.items()]
computelist = []
for cnt in cntlist:
    p = cnt
    if cnt % 2:
        p -= 1
    comp = 0
    for i in range(p, -1, -2):
        comp += math.comb(cnt, i) ## compute C cnt i
    computelist.append(comp)
ans = (reduce((lambda x, y: x*y), computelist) - 1) % MOD
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19