1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

思路

关键观察: 只要sss 中有某个字母出现至少 222 次,就能取这两个位置各自形成长度为 111 的子串(例如两个 aaa),这两个子串显然字符构成相同,答案为 Yes。 反之,若 sss 中每个字母都只出现 111 次,则:

  • 设存在两个不同的子串 s[i,..,i+k−1]s[i,..,i+k-1]s[i,..,i+k−1] 与 s[j,..,j+k−1]s[j,..,j+k-1]s[j,..,j+k−1](k≥1k \ge 1k≥1、i≠ji \ne ji=j)互为异位词。
  • 因为整个 sss 内所有字母都只出现 111 次,所以这两个子串包含的字母集合完全相同就意味着它们包含 同一组唯一的位置。
  • 但两个长度为 kkk 的连续区间若覆盖的是同一组位置,则只能是同一段,即必须有 i=ji=ji=j,与 i≠ji \ne ji=j 矛盾。

P3747.第2题-非空子串

    1000ms Tried: 66 Accepted: 23 Difficulty: 3 所属公司 : 科大讯飞
    算法与标签>字符串

题目内容

ZeemanZeemanZeeman 有一个长度为nnn 的由小写字母组成的字符串sss ,ZeemanZeeman Zeeman想知道,是否存在两个不同的非空子串,它们由完全相同的字符构成(即字符种类和数量完全一致)。

输入描述

第一行输入一个整数n(1≤n≤106)n(1≤n≤10^6) n(1≤n≤106)。

第二行输入一个仅由小写字母组成的字符串 sss。

输出描述

如果存在这样的两个子串,输出 YesYesYes;否则输出 NoNoNo。

样例1

输入

3
abc

输出

No

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 42ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?