<image> It's the end of July – the time when a festive evening is held at Jelly Castle!…
- User
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 s1s2... sn are given, where si 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).
Examples
Input
5 1 AABBB
Output
NO
Input
5 1 ABABB
Output
YES
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.
Assistant
We need to understand problem: There are 26 entrances (A-Z). Guests arrive in order given by string s of length n. Each guest has an assigned entrance (letter). The doors for an entrance are opened right before the first guest that uses that entrance arrives, and closed right after the last guest that uses that entrance arrives. No two guests enter simultaneously. We have k guards. A guard can be assigned to a door when it is opened, and must stay there until the door is closed. At any moment, if number of currently open doors exceeds k, then there is a moment when a door was unguarded (since only k guards). We need to output "YES" if there is such moment (i.e., more than k doors opened simultaneously at some point), otherwise "NO".
Given that doors open and close at times corresponding to guest arrivals, and that only one guest enters at a time, we can think of timeline: At each time before the first arrival of a particular letter, its door is closed; exactly at the time right before the first guest with that letter arrives, the door opens. After the last guest with that letter arrives, the door closes right after that guest's arrival (presumably immediately after). Since no two guests simultaneous, we can model open doors at each interval between arrivals? More precisely, we need to consider times between events: Before first guest arrival, all doors closed. Then for each guest arrival in order, we have: door for that guest's letter must be opened if not already open (it opens right before this guest's arrival). After the guest enters, if this guest is the last one with that letter, then the door closes right after this guest's arrival (i.e., after he enters). So the door is open during the interval from just before the first occurrence of that letter to just after the last occurrence of that letter.
We need to check if at any point in time the number of simultaneously open doors exceeds k. Since doors only change state at times just before a guest arrival (open) and just after a guest arrival (close). The moments of interest are the intervals between these events. But we can check at each event (just before an arrival, just after a departure) the count. However, a simpler way: This is analogous to checking if the maximum number of overlapping intervals (where each interval corresponds to the opening period of a door) exceeds k. Each interval: start = index of first occurrence of letter L (position i, but "right before" that occurrence, so we can treat start as just before that index, but for overlapping counting it's equivalent to considering that the interval is open from the time of first occurrence (including the moment right before that guest enters) until the time after the last occurrence (including the moment after that guest enters). Since guests are discrete events, we can consider times between events.
One approach: For each letter, find its first and last occurrence in the string. Then we have intervals [first[i], last[i]] (in terms of guest indices). However careful: The door is open from just before the first occurrence (so at the moment right before that first guest arrives, door opens; if another guest arrives at the same time? No). So if we consider integer time points representing before arrival of guest i, after guest i, etc., we can map: At time 0 (before any guests), all closed. Then for each guest i from 1 to n, we have a moment just before guest i: before(i). At that moment, if guest i's door is not already open, it opens. Then guest i enters. Then just after guest i: after(i). At that moment, if guest i is last occurrence, its door closes.
Thus doors are open during intervals: open at before(first) and close at after(last). So the door is open for all times between those events. In a discrete event simulation, we can think of scanning from left to right and maintain count of doors currently open. At each i (guest arrival), we need to consider that before processing guest i, we open the door if its first occurrence (i.e., if this is the first time we see that letter, then we open it). That increases count by 1. Then after processing guest i, if this is the last occurrence, we close the door, decreasing count by 1. So if at any time the count exceeds k, we output YES.
But careful: The count after opening (just before guest i) could exceed k. Also the count after closing (just after guest i) might exceed k? Closing reduces count, so only after opening might increase. But we also need to consider that before opening, count was lower. However, there could be a scenario where the door is already open, and we don't increase count. So the only times the count changes are at these events. So we can simulate as:
-
Parse the string, compute for each letter its first and last occurrence indices. We can do in one pass: first_occurrence[26] initialized to INF or -1; last_occurrence[26] initialized to -1. Iterate i from 0 to n-1 (0-indexed). For character ch, if first[ch] not set, set first[ch] = i. Set last[ch] = i.
-
Then we have intervals [first[ch], last[ch]] for each letter that appears.
-
Now we need to compute maximum number of overlapping intervals at any point. Overlap counting: For each index i (guest position), we need to consider whether intervals cover the point between events. Since intervals are inclusive? Let's think: The door is open from just before first occurrence to just after last occurrence. If we consider integer timeline representing the moments before/after each guest as separate, we can treat intervals as covering the "time segments". A typical solution for this problem (CF 834B?) uses a sweep line: for each position i, we note if a door opens at i (i.e., i is first occurrence) and closes after i (i.e., i is last occurrence). Then we can maintain a counter: iterate i from 0 to n-1, at each i if s[i] is first occurrence, increment count. Check if count > k. Then if s[i] is last occurrence, decrement count after processing? But careful: If the door opens at i (just before guest i), then after guest i, if i is also last occurrence, the door closes immediately after guest i. So the door is open only for the duration that includes the moment during guest i? Actually, we need to check if at any moment count > k. The moment just before guest i (after opening) and the moment during guest i (while guest enters) and the moment just after guest i (before closing if last) may be considered. But since no two guests simultaneous, the only times when count could exceed k is after an opening before a possible closing at the same index. If a letter appears only once, then the door opens just before that guest, and closes just after that guest. So it is open for a very short period, but still counts. So if we have many distinct letters each with a single occurrence, then at the moment just before each guest, if multiple doors are open? But for single occurrence letters, they open before their own guest and close after that same guest. That means that for guest i, the door for its letter opens before guest i. However, after guest i, that door closes. So at the moment just before guest i, other doors that are still open from previous guests (if their last occurrence is after i) remain open. So the count at before(i) = number of letters whose intervals cover time just before i. This includes letters whose first occurrence <= i? Actually, if we consider the point just before guest i, it is after any events of previous guests (i-1). For a letter L, its interval is open from before(first) to after(last). For time just before guest i, the interval is open if first(L) <= i? Let's reason: For a letter L, if its first occurrence is at index f, the door opens just before f. So for any time before f, door is closed. For time just before guest i (with i > f), the door is open because it opened before f and remains open until after last. However, if i = f, then just before guest f, the door is about to open. Actually, we open it exactly at that moment. So at just before f, the door is open. So condition: For time just before i, a letter L's door is open if f <= i? And also if l >= i? Wait: If its last occurrence is at l, then door closes just after l. So for time just before i, if i <= l? Because after l, door is closed. So at time just before i, if i > l, then door is already closed? But just before i, if i > l, that means we are at time after the closing of door (which happens after guest l). Since i > l, the closing event (after guest l) has already occurred before time just before i? Actually events: After processing guest l, we close the door. Then we move to next guest (l+1) and just before that guest, we consider the door closed. So for time just before i, door is open if f <= i <= l? Because if i is between f and l inclusive? But careful: For i = f, before f, we open door. So at that moment, door is open. For i = l, before l, door is open. For i = l+1, before l+1, door is closed because after l we closed it. So condition: open if f <= i <= l? Actually, what about the moment just after l? That is after guest l, but before moving to next guest? That moment is not considered in the before events for l+1? We also need to consider if count > k could happen at that moment (just after closing). But that moment has same count as after closing, which is less than before. So max count will be captured at some before(i) or perhaps at some after(i) if after closing there is also opening? But at after(i), after processing guest i, we might have just closed some door but also might have just opened? However opening occurs before guest i, not after. So after guest i, we may only close (if i is last). So count after closing is less than or equal to count before. So maximum count will be at some before(i). So we just need to check count at each before(i). At before(i), we open the door if i is first occurrence of that letter (i.e., we haven't opened it before). Then count becomes previous count + 1. So we can simulate:
Initialize count = 0. Keep an array first[26] and last[26] precomputed. Also a boolean opened[26] = false to track if door is already open? Actually we don't need opened if we know first and last: we can at each i check if i == first[ch]; if yes, we increment count. Then check if count > k -> YES. After that, we need to decrement if i == last[ch]? But careful: The door is still open during the guest's entry and after until after closing. If we decrement immediately after checking, we might be reducing count before the period where the door is still open for that guest? The count at before(i) includes this door because it opened just before i. The door remains open until after last. So for the rest of the timeline (until after last), it should be counted. So if we decrement at i when i == last[ch], we need to consider whether that decrement should happen after the door closes, i.e., after we have passed the moment just after i. In the simulation scanning i from 0 to n-1, we can model that after processing guest i, we close if it's last. So if we decrement after processing the check for before(i), that would effectively reduce count for subsequent i+1 (before i+1). That's correct because after closing, the door is closed before next guest. So we can do:
for i from 0 to n-1: ch = s[i] if i == first[ch]: count++ if count > k: output YES and exit if i == last[ch]: count--
After loop, if never exceeded, output NO.
But is this correct? Let's test with samples.
Sample1: n=5,k=1, s=AABBB. Compute first: A:0, B:2. last: A:1, B:4. i=0: ch=A, i==first[A]? yes => count=1; check count>1? no; i==last[A]? i=0==1? no. i=1: ch=A, i==first[A]? no; count remains 1; check count>1? no; i==last[A]? i=1==1? yes => count=0. i=2: ch=B, i==first[B]? yes => count=1; check count>1? no; i==last[B]? i=2==4? no. i=3: ch=B, i==first? no; count=1; check>1? no; last? 3==4? no. i=4: ch=B, i==first? no; count=1; check>1? no; last? i==4 => count=0. Never >1 => NO.
Sample2: n=5,k=1, s=ABABB. first: A:0, B:1? Actually positions: 0:A,1:B,2:A,3:B,4:B. So first A=0, B=1. last: A=2, B=4. i=0: ch=A, first A => count=1; check>1? no; last A? 0==2? no. i=1: ch=B, first B => count=2; check count>1? 2>1 => YES. So output YES. That matches.
Edge cases: Suppose a letter appears only once, e.g., n=1,k=0, s=A. Then first[A]=0, last[A]=0. i=0: first => count=1; check count>0? 1>0 => YES. That seems plausible: We have 0 guards but one door opens, so unguarded. Output YES. Good.
Suppose n=2,k=1, s=AB. first A=0,last A=0; first B=1,last B=1. i=0: count=1, check>1? no; last A => count=0. i=1: first B => count=1; check>1? no; last B => count=0. Never >1, so NO. That means with one guard, doors open at distinct times: A opens before guest1, closes after guest1; then B opens before guest2, closes after guest2. Since they are not simultaneously open, one guard can manage. So correct.
Now consider overlapping intervals where one door opens before another closes, but with multiple simultaneous doors. The simulation should capture max count.
But need to verify that the condition "if i == first[ch]" increment before check is correct: At time just before guest i, if it's the first occurrence, we open door. So count becomes previous count + 1. That's what we do.
But what about a scenario where a door is already open because its first occurrence was earlier, but we might incorrectly open again? We check i==first to avoid double counting.
Now, do we need to consider that a door might open and close at the same guest? That is, first == last, we increment then after check we decrement. That means for that guest, the door is open for the period just before the guest, and closed just after. The count at before(i) includes it. That's correct.
Now, complexity: O(n). n up to 10^6, fine.
But careful: Implementation must handle large input efficiently. Use arrays of size 26, store first as some sentinel (like -1) and last as -1. Compute while reading string. Then second pass for simulation.
We can even do it in one pass without storing whole string? Because we need first and last occurrences for each letter. That requires scanning the string to compute first and last, then second scanning for simulation. But we could also simulate in one pass with some data structures? But we can store string (up to 1e6 chars) which is fine. Or we can compute first and last in first pass, then simulate. That's O(n) memory for string if we store it; but we can also compute first/last and then read again? Since input is from stdin, we would need to re-read. But we can just store string in a vector or array. 1e6 chars is ~1 MB, fine.
Alternative: One pass using a set or something to track opening and closing events? We could precompute for each position if it's first or last. That can be done with first array and last array.
Thus solution: read n,k, then s. Precompute first[26] with INF (e.g., n) and last[26] with -1. Loop i from 0 to n-1, ch index = s[i]-'A'. If first[ch] > i (or == INF) set first[ch]=i; set last[ch]=i. After loop, then simulate as described.
But careful: Some letters may not appear; first for them may remain INF. We ignore them.
Now we need to output "YES" or "NO".
Check correctness with more tests.
Consider n=3,k=2, s="ABC". first A=0,B=1,C=2; last same. Sim: i=0: count=1; check>2? no; last? 0!=? no decrement? (since last=0, yes: i==last A -> count=0). i=1: count=1; check>2? no; last B -> count=0. i=2: count=1; check>2? no; last C -> count=0. max=1<2 => NO. With 2 guards and 3 doors that open one at a time, never exceed 2, so OK.
Consider n=3,k=1, s="ABA". first A=0, B=1; last A=2, B=1. Sim: i=0: first A => count=1; check>1? no; last A? no. i=1: first B => count=2; check>1? 2>1 => YES. So unguarded. Indeed: A opens before guest1; door A remains open until after guest3 (since last A=2). B opens before guest2, and closes after guest2 (since last B=1). At time just before guest2, both A and B are open, so need 2 guards, only 1 => unguarded. Good.
Consider n=4,k=2, s="ABCA". first A=0, B=1, C=2; last A=3, B=1, C=2. Sim: i=0: count=1; check>2? no; last A? no. i=1: first B => count=2; check>2? no; last B? i=1 => count=1. i=2: first C => count=2; check>2? no; last C? i=2 => count=1. i=3: (A) not first, count=1; check>2? no; last A? i=3 => count=0. max=2 => NO. But is there a moment with 3 open? Let's examine: A open from before guest1 to after guest4. B open from before guest2 to after guest2. C open from before guest3 to after guest3. At before guest2: A open, B opens => 2. At before guest3: A open, C opens => 2 (since B closed after guest2). So never 3. So NO correct.
Now consider n=2,k=1, s="AA". first A=0, last A=1. Sim: i=0: first => count=1; check>1? no; last? no. i=1: not first, count=1; check>1? no; last? i=1 => count=0. So max=1 => NO. With 1 guard, door A open from before guest1 to after guest2, only one door => fine.
Now consider scenario where count might exceed after decrement? No, decreasing never increases.
Thus solution seems correct.
But wait, are there any pitfalls? The problem statement: "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." So the door is opened right before the first guest, and closed right after the last guest. That's exactly what we used. Also: "No two guests can enter the castle simultaneously." So our discrete time model holds.
Now, the condition "if at least one door was unguarded during some time" means there existed a time when number of opened doors > k. So we output "YES" if max concurrent open doors > k.
Edge case: k can be up to 26. n up to 1e6. Input string contains uppercase letters only.
Implementation details:
-
Read n and k as ints.
-
Read string s (maybe with spaces? No, second line contains string of length n). Use cin or getline. Ensure we read correctly. Since n and k on first line, then s on second line. Could be large, use scanf for speed? We can use cin with ios_base::sync_with_stdio(false); cin.tie(0); to speed.
-
Compute first[26], initialize with -1 or n; and last[26] with -1.
-
Loop i=0..n-1: idx = s[i] - 'A'; if (first[idx] == -1) first[idx] = i; last[idx] = i;
-
Then second loop: count = 0; for i=0..n-1: idx = s[i]-'A'; if (i == first[idx]) count++; if (count > k) { output "YES"; return 0; } if (i == last[idx]) count--;
-
After loop, output "NO".
But note: In the second loop, after we decrement, we don't check count > k because decrement reduces, but we might need to check at the moment after closing? But as argued, max is at before(i) or during? Actually, could there be a scenario where after closing, we still have high count? But after closing, count is lower. So maximum is at before opening. Also consider the moment just after closing but before the next opening? That is same as before next guest. So checking before(i) covers all moments.
But careful: The decrement occurs after we process i and before i+1. At the moment just after i (after closing), count may be same as before next? Actually, after closing, the count is decreased. The next check (before i+1) will be after potential openings. So the only times count increases are at openings, which happen at before(i). So yes, checking after each increment is enough.
But what about the possibility that after the last guest, there might be doors still open? The doors close right after the last guest of that letter. For the last guest overall, after his entrance, if that guest is not the last of his letter? Actually, if the last guest (i=n-1) is not the last occurrence of its letter? That cannot be, because it's the last occurrence in the string by definition. So after processing i=n-1, we will decrement if it's last. After loop, all doors are closed. So no issue.
Thus solution is correct.
Time complexity O(n). Memory O(1) for arrays, plus string O(n).
Now, we need to provide final answer.
But I'm ChatGPT, need to output the reasoning and then final answer as code? The user wants solution explanation? The user says: "We need to solve this problem." Possibly expects a code solution. The prompt: "It's the end of July ..." So typical competitive programming problem, we need to write solution.
Thus final response: Explanation and code.
But the user message: "We need to solve this problem." They may want a solution description. We'll provide explanation and then code.
Let's produce final answer: Provide solution approach, then code in C++.
We'll include comments.
Edge cases: If k >= 26, maximum possible distinct doors is 26, so count never >26, but if k >=26, then answer always NO? Actually if k >=26, still could be >k if >26 doors? But only 26 entrances, so max doors is 26. So if k >= 26, answer always NO. But our algorithm will also work.
Now ensure we handle large input efficiently: Use scanf or fast cin.
I'll produce code:
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; string s; cin >> s; vector<int> first(26, -1), last(26, -1); for (int i = 0; i < n; ++i) { int idx = s[i] - 'A'; if (first[idx] == -1) first[idx] = i; last[idx] = i; } int cnt = 0; for (int i = 0; i < n; ++i) { int idx = s[i] - 'A'; if (i == first[idx]) ++cnt; if (cnt > k) { cout << "YES\n"; return 0; } if (i == last[idx]) --cnt; } cout << "NO\n"; return 0; }But we must be careful: first initialized to -1, and we set first only when -1. For letters not appearing, first remains -1. But in the second loop, we check i == first[idx], which for those not appearing (first = -1) won't match any i, fine. For letters that appear, first is set to some index.
However, there is a nuance: If a letter appears multiple times, first is set only at first occurrence, and last at last. That's correct.
Now test on examples:
Input: 5 1 AABBB -> NO 5 1 ABABB -> YES
Works.
Now, I'll produce final answer. ```cpp
#include <bits/stdc++.h> using namespace std;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k; cin >> n >> k; string s; cin >> s; // first and last occurrence of each letter (A=0 .. Z=25) vector<int> first(26, -1), last(26, -1); for (int i = 0; i < n; ++i) { int idx = s[i] - 'A'; if (first[idx] == -1) first[idx] = i; last[idx] = i; } int openDoors = 0; for (int i = 0; i < n; ++i) { int idx = s[i] - 'A'; // door opens just before this guest if it's the first occurrence if (i == first[idx]) ++openDoors; // more than k open doors at this moment -> unguarded if (openDoors > k) { cout << "YES\n"; return 0; } // door closes just after this guest if it's the last occurrence if (i == last[idx]) --openDoors; } cout << "NO\n"; return 0;}
-