求问一个关于字符串的字节面试算法题,优化不出来了

输入两个子串,记作t,p,求t中是否存在p的子串,子串的定义为所含有的元素的数量完全相同,顺序可以不同。若存在,则返回-1,若存在,则返回index。
例如:
输入:
t=CABABBABC
p=ABBC
输出:
5
解析:
CABAB【BABC】中括号的位置为子串

这个题一开始用滑动窗口+字典统计个数AC了,但是面试官说这样的滑动窗口是一个一个往后遍历的,让优化一下(感觉是类似于KMP那种,一次性跳好几个index)
比如当遍历到index=0的时候,个数统计:A=2 B=1 C=1,A的个数超过了p中的A的个数,此时直接将index跳到第二个A,即从index=3继续

实在不知道咋写了,感觉不太好实现,有没有老哥会这个题的,可否提供一下答案呢,谢谢!
#字节面试##字节跳动##笔试题目#
全部评论
排序然后用kmp?
点赞 回复 分享
发布于 2023-02-03 03:19 四川
我觉得可以用双指针ij。大概思路就是逐渐增大ij之间的窗口大小,当大小等于p时就匹配成功了。 每次迭代,j指针指向下一个字符,当下一个字符数量已经超出时,向右移动i至当前字符值的下一个位置。 时间复杂度O(n). 输入: t=CABABBABC p=ABBC 迭代(左右括号代表ij): - []CABABBABC - [C]ABABBABC - [CA]BABBABC - [CAB]ABBABC - CA[BA]BBABC // 此处A的数量已经超出,所以i移动到了第一个A后面 - CA[BAB]BABC - CAB[ABB]ABC// 此处B的数量已经超出,所以i移动到了第一个B后面 - CABA[BBA]BC - CABAB[BAB]C - CABAB[BABC] // ij之间距离==4,return
点赞 回复 分享
发布于 2022-04-11 14:30

相关推荐

05-29 19:11
已编辑
北方民族大学 Java
😭😭😭😭本人26届双非本,后端选手。从25年秋招开始,一直到春招5月份,一共面了12次字节。可以说后面能继续投递面上字节大概率是因为前面一直累计的面评还不错,但是最终的结果往往不尽如人意,黄梁一梦。timeline:如标题,总共面了12次字节,4个不同的岗位。第一次:抖音生活服务测开二面完排序挂第二次:TikTok国际化电商测开三面完排序挂第三次:飞书后端安全团队三面完挂第四次:飞书后端偏基架团队三面完过,HR面完之后询问综合排序不推进。我知道像BAT这样的公司,双非本想拿到一张入场券有多难,也知道每次挂在排序/三面/HR面,那种差一步上岸又被打回原点的落差感有多磨人。可是最后一次字节的这个岗位,已经是5月中旬才开始面得了,春招末期的岗位,我本以为真的缺人,三面过的那天,我真的以为就差一步hr面就稳了,但是,最终的结果很遗憾,综合排序综合排序,不推进了。如果是技术能力的问题,我想也不会每一轮技术面给我通过。思来想去。难道真的就是因为我们双非有案底,所以最后的一切又算什么呢。付出这么多的时间精力,还是抵不过双非学历太差吗?既然如此一开始直接卡掉简历不用给面试不就行了嘛,每一轮面试都给我们生的希望,最后的最后又回到了那个必输的起点。12次字节,说不遗憾是假的,也无数次怀疑过自己:是不是我算法刷得还不够?是不是项目亮点讲得不够好?是不是学历就是一道跨不过去的坎?但回头看,这一年的秋招到春招,从面对面试官紧张到说话卡壳,到后来的从容面对,再到如今甚至能和面试官探讨AI&大模型技术的一些方案思路,我已经比去年的自己强太多了。可能字节于我,真的是一场盛大的单恋,拼尽全力奔赴,却还是没能收到想要的回应。前路漫漫,字节的梦碎了,但我的路还在继续,希望下一站,会有属于我的一场徐风。
不愿吃饼的山羊很友好:你的心理素质是真的强大,如果是我碰到这样都会疯了
点赞 评论 收藏
分享
评论
点赞
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务