All Tracks Algorithms Searching Binary Search Problem

Gaitonde's Revenge

Easy, Implementation, Strings, binary-search, epiphany8.0, medium


Gaitonde wants to take revenge against Sulaiman Isa. So he decides to send an army of characters to attack Isa. He has a team in the form of string \(S\) of \(N\) characters. He has to attack Isa on \(Q\) days. Each of the \(Q\)\(th \) day, Gaitonde has a string \(T\), an integer \(B\) and another integer \(K\). He has to form string \(T\) from string \(S\) so that the order of characters in T must be same as that of S. However starting from the beginning, the characters in \(S\) have divided themselves in groups of \(B\) characters each except the last which has \(\le B\) members.If there are remaining characters in the last, they will form their group. Since Gaitonde wishes to maintain diversity, he will select no more than K members from each group to form \(T\). For each day, your task is to find whether it is possible to form \(T\) from string \(S\) as per rules, so that Gaitonde can attack Isa.

Input Format :- 

  • First line consists of single integer N, denoting the length of string S.
  • Second line consists of string S of length N.
  • Third line consists of single integer Q, denoting the total number of days Gaitonde will attack Isa.
  • Each of the next Q lines consists of string of length M, an integer B, and another integer K. It means that for this query, the string S is divided into groups of B characters, and you are allowed to pick atmost K characters from each group of S so as to form T.
  • All strings will only contain lowecase English letters.

Output Format :- 

  • Print Q lines: The ith line denotes the answer to ith day.
  • Print "Yes" (without quotes) in new line, if it is possible to form string T from S as per rules, else print "No" (without quotes) in a new line.

Constraints :- 

  • \(1 \le N \le 2*10^{5} \)
  • \(1 \le Q \le 10^{5}\)
  • \(1 \le \sum |T| \le 4*10^{5} \) , sum of length of T over all queries Q
  • \(1 \le B \le N \)
  • \(1 \le K \le B\)
abz 3 1
baz 3 2
abbby 3 2
adef 3 2
abxc 5 2
acdxyz 5 2

For queries 1-4, the string is divided as shown.

Sample Image on how string is divided

1) = abz and = 1, You can choose group 1 to form a, group 2 to form b and group 4 to form z. Note that we are choosing at max 1 character from each group.

2) = baz and = 2, It is not possible to form T.

Note, you can't choose first group to form ba and then last group to form z. Since, the order of characters in T must be same as order in string S.

3) = abbby and = 2. Choose group 1 to form a and b, group 2 to form b and b and group 4 to form y.


For queries 5-6, the string is divided as shown.

Image showing how string is divided into blocks of size 5

5) = abxc and = 2, It is not possible to form T.

Note, you can form a and b from 1st group but xc can't be formed.  Since, the order of characters in T must be same as order in string S.

6) = acdxyz and = 2, choose group 1, 2 and 3 to form string T.

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in

NIT Surat

Challenge Name


View All Notifications