MLE · CodeSignal OA Coding

Coinbase 最长连续字符段:同长度取最右边

MLE OA 编程题给字符串,输出最长相同字符连续段的字符与长度;并列必须覆盖旧答案选择最右段。

题目重点:MLE OA 编程题给字符串,输出最长相同字符连续段的字符与长度;并列必须覆盖旧答案选择最右段。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练版按 Unicode code point 遍历字符串,返回 (character,length);若空串返回 (null,0),需以原测试接口为准。
  • 连续段只在相邻字符相同才延长,大小写有别;不做 Unicode 规范化。
  • ‘最右边’指起始索引最大,等长段扫描到较晚位置就更新。

解题路线

  1. 一次线性扫描维护当前段字符、长度和最佳段;遇不同字符先结算旧段,再开始新段。结算时若 currentLength≥bestLength 就更新 best,等号让更右段胜出。
  2. 循环结束必须再结算末段,或在末尾加哨兵;否则最长段在字符串末尾时会漏。
  3. 训练例 `aaabbccc` 有 a 与 c 长度 3,答案 c,3;`aabb` 取 b,2;`ab` 取 b,1。
  4. 若需输出原字符串中的字符索引,可同时记录段起点;多码位 grapheme cluster 的用户可见字符语义要另确认。

手动走一遍

扫描 `aaabbccc`:a 段结算长度 3,best=(a,3);b 段长度 2 不改;末尾 c 段长度 3 与 best 相等,使用 ≥ 更新为 (c,3)。若代码只写 `>` 会错误返回 a。

规模与取舍

n 个 code point 一次扫描 O(n) 时间、O(1) 额外空间;若为了 grapheme cluster 先切分,处理成本依分词库。

易错点与追问

容易失分的边界

  • 仅在严格更长时更新,违反右侧并列。
  • 忘结算末段。
  • 用全局字符出现次数而非最长连续段。
  • 空串直接访问 s[0] 崩溃。

继续深挖

  • 若要求最左边同长度怎么改?
  • 输入按流式 chunk 传来,段跨 chunk 如何处理?
  • Emoji 组合字符如何定义相同字符?
✓已复制微信号!