All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

Kth Character
Tag(s):
No tags
Problem
Editorial
Analytics

Given a string $$S$$ of length $$N$$, you have to answer $$Q$$ queries. Each query includes a range ($$L$$ and $$R$$) and a number $$K$$. For every query to have to print the lexicographically $$K$$th smallest alphabet in the given range.
INPUT

  • The first line includes two integers $$N$$ and $$Q$$. $$N$$ representing the length of the string and $$Q$$ representing the number of queries.
  • Second line contains the string $$S$$.
  • Next $$Q$$ lines contain 3 integers $$L$$, $$R$$ and $$K$$

OUTPUT

The output should contain q lines, each line representing the $$K$$th character in the given range of the query.

CONSTRAINT

  • 1 <= $$N$$ <= 1000000
  • 1 <= $$Q$$ <= 1000000
  • 1 <= $$L$$ <= $$R$$ <= 1000000
  • 1 <= $$K$$ <= $$R$$ - $$L$$ + 1
  • The string consists of small english alphabets
SAMPLE INPUT
10 5
ababcdabcd
1 4 2
1 4 3
1 5 5
1 10 8
7 10 3
SAMPLE OUTPUT
a
b
c
c
c
Time Limit: 5.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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?