Missing letters


Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 250M

Author:
Problem type

You will be given a string consisting of lowercase English alphabet. Some characters of this string are missing, we would like to know if it is possible to fill those characters with any lowercase letter so that there is a sub-string that contains exactly \(x\) times each character of English alphabet.

Input Specification

The input start with one line containing one integer denoting the number of test cases. Each test case consists of a line containing an integer \(x\) (\(1 \leq x \leq 10^5\)) and a string S (\( 1 \leq |S| \leq 10^5\), S contains only lowercase English alphabet or a question mark ('?'). A question mark indicates a missing character.)

Output Specification

For each test case output one line containing "YES" (without the quotes) if it's possible to have a substring that contains exactly \(x\) times each character of the English alphabet. Otherwise output "NO".

Scoring

  • (\( 1 \leq x, |S| \leq 100\)), 10 points
  • (\( 1 \leq x, |S| \leq 1000\)), 30 points
  • (\( 1 \leq x, |S| \leq 100000\)), 60 points

Sample Input

    2
    2 azertyuiopqsdfghjklmwxcvb???????????????????????????
    1 abcdefghijkllmnopqrstuvwxyz

Sample Output

    YES
    NO

Comments


  • 0
    AkramElOmrani  commented on May 1, 2021, 5:52 a.m.

    Could someone please tell me where my error is, I've been trying to debug for 3 hours now.I am sure my sliding window implementation is correct but it keeps giving me wrong answer