具有给定约束的子字符串数
具有给定约束的子字符串数
提问于 2016-08-06 20:50:58
我被赋予一个排序字符串，我希望计数在以下约束下可能的子字符串数量(不一定是连续的)：
- 子字符串中的所有字母都应按排序顺序排列。
- 子字符串只能包含一个元音。
- 子字符串的长度应该大于或等于3。
例如：
对于"aabbc"，我们有三个子字符串“abc”、"abb“、"abc"，它们与上面的constraints.So相匹配，这里3是ans。
我该怎么做才能得到一根普通的绳子？
我已经试了2-3个小时了，但是找不到合适的方法。我今天在一次程序编码中被问到了这个问题，我担心明天的面试中也会问同样的问题。即使是暗示或方法，也将不胜感激。
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-08-06 21:19:51
假设我们有k个元音，一个数组A指定每个非元音的直方图。(即A[0]是第一个非元音的数目，A[1]是第二个非元音的数目。)
然后(忽略长度约束)我们对元音有k个选择，对剩下的字母有(A[0]+1)*(A[1]+1)*(A[2]+1)*...选择(对于每个非元音，我们可以有0,1,2,...,A[i]选项)。
这由k(对于单个字母的情况)和k*len(A)对双字母的情况多算，所以从总数中减去这些。
Python代码示例：
from collections import Counter
s='aabbc'
vowels = 'aeiou'
C = Counter(s)
t = 1
vowel_count = 0
cons_count = 0
for letter,count in C.items():
if letter in vowels:
vowel_count += 1
else:
cons_count += 1
t *= count+1
print vowel_count * (t - cons_count - 1)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/38808589
复制相关文章
相似问题
腾讯云开发者
