头条面试手撕代码题目求解答
给定一个字符串，由大写字母组成，相同字母连续出现，如"AAABBCC","HBBA",求给定字符串有多少个不同的子串。
如"HBBA"有"H","B","A","HB","BB","BA","HBB","BBA","HBBA"总共9个不同的子串
#字节跳动#
2017-09-12 17:58 已编辑 四川大学 Java
关注
全部评论
JimmyWuu
西安电子科大 Java
我有个两层for循环的方法不知当讲不当讲……
sheeco
四川大学 C++
遍历一遍统计每个数及其出现次数k。序列总长度n，则子串一共有1+...+n=n(n+1)/2个。重复的子串只会出现在每个重复字符自己的范围内，比如AAAA(k=4): 长度1的子串有4个，需要减掉重复的3(=k-1)个只留下1个；长度2的有3个，需要减掉2(=k-2)个...直到长度k-1的子串有2个，需要减掉1个。即一共需要减掉(k-1)+...+1=k(k-1)/2个。对每个求出的k都把这个减掉就可以了，验证AAABBCC答案是28-3-1-1=23个，不知道对不对？
牛客594283号
电子科技大学 前端工程师
什么岗位呀
牛客437355号
东北大学 C++
先去重，记录下重复的字母以及个数，一个字母表示一个位，然后就是组合数的加法，随后把重复的字母看成一个整体，加上必选这个的组合数。。。依次往上加就行了
丝瓜3
同济大学 C++
这题如果没有题目里相邻的字符的限制的话，最优解法应该是楼上说的O（n）用DC3求后缀数组，然后扫一遍height出答案。然后有限制的话就比较简单了... 所有子串的数量是C(n,2) + n，但是其中会有重复的，考虑减去重复的。对于连续的一种字符，设其长度为k，则重复的数量是C(k,2) + k - k，从头到尾扫一遍，遇到新字符就统计一下k，然后减掉就好了.. 时间复杂度O(n),空间复杂度O(1)
天涯__
华中科技大学 算法工程师
只有我没看懂题吗？ 对于"AAABBCC"，相同的就是两个“AA” 与 “AA”？
spoj 694
后缀数组
饭炒蛋与蛋炒饭
电子科技大学 Java
对于一个长度为N的字符串，一共有N*(N+1)/2个子串，HBBA一共有10个子串，但里面有一个BB，所以计算时多算一个B，则结果是10-1=9。像BBBA就是10-(2+1)=7。个人想法，不知对不对
梅子青时节
武汉大学
相同字母连续出现，所以先统计每个字符出现的次数，再用个两层for循环就可以算出来啦
牛客第一菜
********* Java
感觉kmp next数组的方法可以解
牛客1171869号
哈尔滨工业大学深圳研究生院 算法工程师
trie呢
要求什么复杂度？
心雨M
蚂蚁集团_支付宝_后台开发
0到length 往set 丢 这样行吗
迭戈·科斯塔
蓝翔 C++
dfs?
相关推荐
OPPO公司福利 1133人发布