A. Doggo Recoloring

Codeforces

IDCF1025A

Time1000ms

Memory256MB

Difficulty—

implementationsortings

English · Original

Chinese · Translation

Formal · Original

Panic is rising in the committee for doggo standardization — the puppies of the new brood have been born multi-colored! In total there are 26 possible colors of puppies in the nature and they are denoted by letters from '_a_' to '_z_' inclusive. The committee rules strictly prohibit even the smallest diversity between doggos and hence all the puppies should be of the same color. Thus Slava, the committee employee, has been assigned the task to recolor some puppies into other colors in order to eliminate the difference and make all the puppies have one common color. Unfortunately, due to bureaucratic reasons and restricted budget, there's only one operation Slava can perform: he can choose a color $x$ such that there are currently **at least two** puppies of color $x$ and recolor **all** puppies of the color $x$ into some arbitrary color $y$. Luckily, this operation can be applied multiple times (including zero). For example, if the number of puppies is $7$ and their colors are represented as the string "_abababc_", then in one operation Slava can get the results "_zbzbzbc_", "_bbbbbbc_", "_aaaaaac_", "_acacacc_" and others. However, if the current color sequence is "_abababc_", then he can't choose $x$\='_c_' right now, because currently only one puppy has the color '_c_'. Help Slava and the committee determine whether it is possible to standardize all the puppies, i.e. after Slava's operations all the puppies should have the same color. ## Input The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of puppies. The second line contains a string $s$ of length $n$ consisting of lowercase Latin letters, where the $i$\-th symbol denotes the $i$\-th puppy's color. ## Output If it's possible to recolor all puppies into one color, print "_Yes_". Otherwise print "_No_". Output the answer without quotation signs. [samples] ## Note In the first example Slava can perform the following steps: 1. take all puppies of color '_a_' (a total of two) and recolor them into '_b_'; 2. take all puppies of color '_d_' (a total of two) and recolor them into '_c_'; 3. take all puppies of color '_b_' (three puppies for now) and recolor them into '_c_'. In the second example it's impossible to recolor any of the puppies. In the third example all the puppies' colors are the same; thus there's no need to recolor anything.

委员会中关于狗标准的恐慌情绪正在上升——新一窝小狗出生时毛色各异！自然界中总共有 26 种可能的毛色，分别用字母 '_a_' 到 '_z_' 表示。委员会的规则严格禁止任何微小的差异，因此所有小狗必须具有相同的颜色。为此，委员会工作人员 Slava 被分配了任务：通过将一些小狗重新染色为其他颜色，消除差异，使所有小狗拥有同一种颜色。然而，由于官僚原因和预算限制，Slava 只能执行一种操作：他可以选择一种颜色 $x$，使得当前至少有两个小狗的颜色为 $x$，然后将所有颜色为 $x$ 的小狗重新染成任意一种颜色 $y$。幸运的是，这种操作可以多次执行（包括不执行）。例如，如果小狗数量为 $7$，它们的颜色表示为字符串 "_abababc_"，那么在一次操作中，Slava 可以得到 "_zbzbzbc_"、"_bbbbbbc_"、"_aaaaaac_"、"_acacacc_" 等结果。但是，如果当前颜色序列为 "_abababc_"，他不能选择 $x$='_c_'，因为当前只有一个小狗的颜色是 '_c_'。请帮助 Slava 和委员会判断是否可能将所有小狗标准化，即经过 Slava 的操作后，所有小狗都具有同一种颜色。第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 小狗的数量。第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成，其中第 $i$ 个字符表示第 $i$ 只小狗的颜色。如果可以将所有小狗重新染成同一种颜色，请输出 "_Yes_"。否则输出 "_No_"。请不要输出引号。在第一个例子中，Slava 可以执行以下步骤：在第二个例子中，无法对任何小狗进行重新染色。在第三个例子中，所有小狗的颜色都相同；因此无需重新染色。 ## Input 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 小狗的数量。第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成，其中第 $i$ 个字符表示第 $i$ 只小狗的颜色。 ## Output 如果可以将所有小狗重新染成同一种颜色，请输出 "_Yes_"。否则输出 "_No_"。请不要输出引号。 [samples] ## Note 在第一个例子中，Slava 可以执行以下步骤：选择所有颜色为 '_a_' 的小狗（共两个），将它们重新染成 '_b_'；选择所有颜色为 '_d_' 的小狗（共两个），将它们重新染成 '_c_'；选择所有颜色为 '_b_' 的小狗（此时共有三个），将它们重新染成 '_c_'。在第二个例子中，无法对任何小狗进行重新染色。在第三个例子中，所有小狗的颜色都相同；因此无需重新染色。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of puppies. Let $ s \in \{a, b, \dots, z\}^n $ be a string representing the initial colors of the puppies. Let $ C \subseteq \{a, b, \dots, z\} $ be the set of distinct colors present in $ s $. For each color $ c \in C $, let $ f(c) = |\{i \in \{1, \dots, n\} \mid s_i = c\}| $ denote the frequency of color $ c $. **Constraints** 1. $ 1 \le n \le 10^5 $ 2. Each character in $ s $ is a lowercase Latin letter (i.e., from 'a' to 'z'). **Operation** In one move, choose a color $ x \in C $ such that $ f(x) \ge 2 $, and replace all occurrences of $ x $ with any color $ y \in \{a, b, \dots, z\} $ (possibly $ y \notin C $, but the result must remain a multiset of colors from $ \{a, b, \dots, z\} $). This operation reduces the size of $ C $ by one if $ y \notin C $, or leaves $ |C| $ unchanged if $ y \in C \setminus \{x\} $. **Objective** Determine whether it is possible to perform a finite sequence of such operations to reduce $ C $ to a singleton set (i.e., all puppies have the same color). **Answer Condition** It is possible to standardize all puppies if and only if: $$ |C| = 1 \quad \text{or} \quad \exists\, c \in C \text{ such that } f(c) \ge 2 $$ Equivalently: $$ \boxed{\text{Yes}} \quad \text{if and only if} \quad |C| = 1 \quad \text{or} \quad \max_{c \in C} f(c) \ge 2 $$ $$ \boxed{\text{No}} \quad \text{otherwise} $$

Samples

Input #1

6
aabddc

Output #1

Yes

Input #2

3
abc

Output #2

No

Input #3

3
jjj

Output #3

Yes

API Response (JSON)

{
  "problem": {
    "name": "A. Doggo Recoloring",
    "description": {
      "content": "Panic is rising in the committee for doggo standardization — the puppies of the new brood have been born multi-colored! In total there are 26 possible colors of puppies in the nature and they are deno",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1025A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Panic is rising in the committee for doggo standardization — the puppies of the new brood have been born multi-colored! In total there are 26 possible colors of puppies in the nature and they are deno...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "委员会中关于狗标准的恐慌情绪正在上升——新一窝小狗出生时毛色各异！自然界中总共有 26 种可能的毛色，分别用字母 '_a_' 到 '_z_' 表示。\n\n委员会的规则严格禁止任何微小的差异，因此所有小狗必须具有相同的颜色。为此，委员会工作人员 Slava 被分配了任务：通过将一些小狗重新染色为其他颜色，消除差异，使所有小狗拥有同一种颜色。\n\n然而，由于官僚原因和预算限制，Slava 只能执行一种操作...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of puppies.  \nLet $ s \\in \\{a, b, \\dots, z\\}^n $ be a string representing the initial colors of the puppies.  \nLet $ C \\subseteq \\{a, b, \\dots,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments