"你叉叉,唱日出,穷哈哈,唱日落.....",小哈开心地哼着小调,因此小哈是一个爱笑的人,每次笑都很有魔性,调皮地小哼记录了小哈的一次说的话,其中里面可能包含了小哈的笑声,并以为字符串来记录小哈的话。已知,小哈的笑声是字母 a 和 h 交替的序列,例如: ahahah , aha , a , h 是符合笑声的合法序列。但是, abacaba , aa 不符合笑声的合法序列。 通过小哼的记录,请你求出小哈笑声的最大长度。
输入的第一行给出小哈说话的长度 N 。 随后一行中输入一行长度为 N 字符串 S ——表示小哈的话。 1 ≤ N ≤ 10^5 S 仅由小写字母组成。
输出小哈笑声的最大长度。
7 abacaba
1
20 ahahahahahahahahahah
20
考点:字符串 · 双指针
数据规模 N ≤ 1e5 | 限制 1 秒 / 256MB | 标准输入输出
推荐方向:双指针
用两个指针协同移动,把两层循环的 O(n²) 优化到 O(n)。
思路框架(双指针 通法 · 非本题专属)
实现要点:写成 while (l < r) 循环最清晰,切记每轮至少有一个指针移动,否则死循环。
复杂度:时间 O(n)(排序则 O(n log n)) | 空间 O(1)
该范式的通法易错点
对照本题
样例 1
7 / abacaba1样例 2
20 / ahahahahahahahahahah20解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2024年春招-京东-技术通用岗位-第二批笔试。