京东 · 哈希 · 算法编程题
京东 哈希 时限 1 秒 / 256 MB

题目描述

给出一个仅由字符 AB 构成的字符串 Str
请你求出 S 中包含 A 和 B 个数相同的连续区间的最长长度。

输入输出

输入描述
输入的第一行给出字符串 S 。
1 ≤ S.len() ≤ 2 × 10^5
输出描述
输出 S 中包含 A 和 B 个数相同的连续区间的最长长度。

样例共 2 组

样例 1
输入
AAAAAA
输出
0
样例 2
输入
AAABBBBAAABBB
输出
12

算法解析依据充分

考点:字符串 · 哈希 · 前缀和

限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:哈希

用哈希表把「查找/计数」的开销降到 O(1) 均摊。

思路框架(哈希 通法 · 非本题专属)

  1. 一次遍历,把元素作为 key、出现次数/首次位置作为 value 存进哈希表。
  2. 第二次遍历(或边扫边查)拿到需要的信息。
  3. 注意哈希无序:需要按原顺序输出时要额外记录顺序。

实现要点:Python 用 dict / collections.Counter / defaultdict;C++ 用 unordered_map。

复杂度:时间 O(n) 均摊 | 空间 O(n)

该范式的通法易错点

  • 遍历哈希表时依赖了不存在的顺序。
  • 多次查询时每次都重新统计。

样例

样例 1

  • 输入:AAAAAA
  • 输出:0

样例 2

  • 输入:AAABBBBAAABBB
  • 输出:12

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2024年春招-京东-技术通用岗位-第四批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解