B. The Festive Evening

Codeforces
IDCF834B
Time1000ms
Memory256MB
Difficulty
data structuresimplementation
English · Original
Chinese · Translation
Formal · Original
<center>![image](https://espresso.codeforces.com/6fa174fdf0ed7a199b9c338432628d2824b432fc.png)</center>It's the end of July – the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it's a necessity to not let any uninvited guests in. There are 26 entrances in Jelly Castle, enumerated with uppercase English letters from _A_ to _Z_. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest's arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously. For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There are _k_ such guards in the castle, so if there are more than _k_ opened doors, one of them is going to be left unguarded! Notice that a guard can't leave his post until the door he is assigned to is closed. Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more than _k_ doors were opened. ## Input Two integers are given in the first string: the number of guests _n_ and the number of guards _k_ (1 ≤ _n_ ≤ 106, 1 ≤ _k_ ≤ 26). In the second string, _n_ uppercase English letters _s_1_s_2... _s__n_ are given, where _s__i_ is the entrance used by the _i_\-th guest. ## Output Output «_YES_» if at least one door was unguarded during some time, and «_NO_» otherwise. You can output each letter in arbitrary case (upper or lower). [samples] ## Note In the first sample case, the door A is opened right before the first guest's arrival and closed when the second guest enters the castle. The door B is opened right before the arrival of the third guest, and closed after the fifth one arrives. One guard can handle both doors, as the first one is closed before the second one is opened. In the second sample case, the door B is opened before the second guest's arrival, but the only guard can't leave the door A unattended, as there is still one more guest that should enter the castle through this door.
七月末到了——果冻城堡举行节日晚会的时候!来自王国各地的宾客齐聚于此,讨论糖果界的最新潮流。然而,这里讨论的一些内容并不适合向公众公开:如果这些信息落入别有用心者之手,可能会在甜点王国引发动荡。因此,必须防止任何未受邀的宾客进入。 果冻城堡共有26个入口,用大写英文字母_A_到_Z_编号。由于安全措施,每位宾客都被分配了一个特定的入口进入城堡。每个入口的门会在第一个宾客到达前立即打开,并在最后一个应通过该入口进入的宾客到达后立即关闭。任何两个宾客都不能同时进入城堡。 为了防止可能的入侵,每个入口都需要一名糖果守卫看守。城堡中一共有#cf_span[k]名守卫,因此如果同时打开的门超过#cf_span[k]个,就必定有一个门无人看守!注意,守卫必须坚守岗位,直到他负责的门关闭为止。 Slastyona怀疑晚会上可能有未受邀的宾客。她知道受邀宾客进入城堡的顺序,希望你帮助她检查是否存在某个时刻,打开的门超过了#cf_span[k]个。 第一行给出两个整数:宾客数量#cf_span[n]和守卫数量#cf_span[k](#cf_span[1 ≤ n ≤ 106],#cf_span[1 ≤ k ≤ 26])。 第二行给出#cf_span[n]个大写英文字母#cf_span[s1s2... sn],其中#cf_span[si]表示第#cf_span[i]位宾客使用的入口。 如果存在某个时刻至少有一个门无人看守,则输出«_YES_»,否则输出«_NO_»。 你可以以任意大小写形式输出每个字母。 在第一个样例中,门A在第一位宾客到达前打开,在第二位宾客进入城堡时关闭。门B在第三位宾客到达前打开,在第五位宾客到达后关闭。一名守卫可以同时看守这两扇门,因为第一扇门在第二扇门打开前已经关闭。 在第二个样例中,门B在第二位宾客到达前打开,但唯一的守卫无法离开门A,因为仍有一位宾客需要通过门A进入城堡。 ## Input 第一行给出两个整数:宾客数量#cf_span[n]和守卫数量#cf_span[k](#cf_span[1 ≤ n ≤ 106],#cf_span[1 ≤ k ≤ 26])。第二行给出#cf_span[n]个大写英文字母#cf_span[s1s2... sn],其中#cf_span[si]表示第#cf_span[i]位宾客使用的入口。 ## Output 如果存在某个时刻至少有一个门无人看守,则输出«_YES_»,否则输出«_NO_»。你可以以任意大小写形式输出每个字母。 [samples] ## Note 在第一个样例中,门A在第一位宾客到达前打开,在第二位宾客进入城堡时关闭。门B在第三位宾客到达前打开,在第五位宾客到达后关闭。一名守卫可以同时看守这两扇门,因为第一扇门在第二扇门打开前已经关闭。在第二个样例中,门B在第二位宾客到达前打开,但唯一的守卫无法离开门A,因为仍有一位宾客需要通过门A进入城堡。
**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of guests. Let $ k \in \mathbb{Z}^+ $ be the number of available guards, $ 1 \leq k \leq 26 $. Let $ S = s_1 s_2 \dots s_n $ be a string of $ n $ uppercase English letters (from 'A' to 'Z'), where $ s_i $ denotes the entrance used by the $ i $-th guest. For each entrance $ c \in \{\text{'A'}, \dots, \text{'Z'}\} $, define: - $ \text{first}(c) = \min\{ i \in \{1, \dots, n\} \mid s_i = c \} $, the index of the first occurrence of $ c $ in $ S $, - $ \text{last}(c) = \max\{ i \in \{1, \dots, n\} \mid s_i = c \} $, the index of the last occurrence of $ c $ in $ S $. If $ c $ does not appear in $ S $, then $ \text{first}(c) = \text{last}(c) = \infty $. Let $ \mathcal{D} = \{ c \in \{\text{'A'}, \dots, \text{'Z'}\} \mid \text{first}(c) < \infty \} $ be the set of distinct entrances used. **Constraints** 1. $ 1 \leq n \leq 10^6 $ 2. $ 1 \leq k \leq 26 $ 3. For all $ i \in \{1, \dots, n\} $, $ s_i \in \{\text{'A'}, \dots, \text{'Z'}\} $ **Objective** Determine whether there exists a time $ t \in \{1, \dots, n\} $ such that the number of entrances $ c \in \mathcal{D} $ for which $ \text{first}(c) \leq t \leq \text{last}(c) $ is strictly greater than $ k $. That is, output "YES" if $$ \max_{t \in \{1, \dots, n\}} \left| \left\{ c \in \mathcal{D} \mid \text{first}(c) \leq t \leq \text{last}(c) \right\} \right| > k, $$ otherwise output "NO".
Samples
Input #1
5 1
AABBB
Output #1
NO
Input #2
5 1
ABABB
Output #2
YES
API Response (JSON)
{
  "problem": {
    "name": "B. The Festive Evening",
    "description": {
      "content": "<center>![image](https://espresso.codeforces.com/6fa174fdf0ed7a199b9c338432628d2824b432fc.png)</center>It's the end of July – the time when a festive evening is held at Jelly Castle! Guests from all o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF834B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "<center>![image](https://espresso.codeforces.com/6fa174fdf0ed7a199b9c338432628d2824b432fc.png)</center>It's the end of July – the time when a festive evening is held at Jelly Castle! Guests from all o...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "七月末到了——果冻城堡举行节日晚会的时候!来自王国各地的宾客齐聚于此,讨论糖果界的最新潮流。然而,这里讨论的一些内容并不适合向公众公开:如果这些信息落入别有用心者之手,可能会在甜点王国引发动荡。因此,必须防止任何未受邀的宾客进入。\n\n果冻城堡共有26个入口,用大写英文字母_A_到_Z_编号。由于安全措施,每位宾客都被分配了一个特定的入口进入城堡。每个入口的门会在第一个宾客到达前立即打开,并在最后一...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of guests.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of available guards, $ 1 \\leq k \\leq 26 $.  \nLet $ S = s_1 s_2 \\dots s_n $ be a string ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments