思路
关键观察:
只要s 中有某个字母出现至少 2 次,就能取这两个位置各自形成长度为 1 的子串(例如两个 a),这两个子串显然字符构成相同,答案为 Yes
。
反之,若 s 中每个字母都只出现 1 次,则:
- 设存在两个不同的子串 s[i,..,i+k−1] 与 s[j,..,j+k−1](k≥1、i=j)互为异位词。
- 因为整个 s 内所有字母都只出现 1 次,所以这两个子串包含的字母集合完全相同就意味着它们包含 同一组唯一的位置。
- 但两个长度为 k 的连续区间若覆盖的是同一组位置,则只能是同一段,即必须有 i=j,与 i=j 矛盾。
题目内容
Zeeman 有一个长度为n 的由小写字母组成的字符串s ,Zeeman想知道,是否存在两个不同的非空子串,它们由完全相同的字符构成(即字符种类和数量完全一致)。
输入描述
第一行输入一个整数n(1≤n≤106)。
第二行输入一个仅由小写字母组成的字符串 s。
输出描述
如果存在这样的两个子串,输出 Yes;否则输出 No。
样例1
输入
3
abc
输出
No