All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

Yet Another Valentine's Proposal



Toru proposes Hori again this Valentine. Hori being an intelligent girl, gives Toru a long nonsense game so that he stops bothering her.

Hori gives him a string and Q queries.

For each query there are two integers l and r

Toru is supposed to create a new string of 26 characters for each query using following rules:

He needs to count the occurrence of each alphabet from l to r

The 1st position in the new string is for occurrence of ‘a’ , second for ‘b’ and so on.

If ‘a’ occurs x times in the range l to r , the first position in the string will be the x%26 +1, character of the english alphabet.

For each query, Toru needs to determine the longest prefix which is also the suffix of newly created string.


The first line of input contains two integers N and Q denoting length of the string and total number of queries.

The second line contains the string.

Q lines, one for each query follows

For each query, two integers are provided l and r \( 0 \lt l \le r \le N \)


For each query, print the longest prefix which is also a suffix of newly created string. Print Q lines , one for each query. If no such prefix exist, print "None" for that query.


\( 0 \lt l \le r \le N \)

String contains only lowercase English alphabets.

Subtask 1: \(20\) Points

\( 1\le N,Q \le 1000 \)

Subtask 2: \(80\) Points

\( 1\le N,Q \le 50000 \)

Note : Do not consider the whole string as prefix or suffix.

26 1
1 26

Every alphabet is present once in the string

Hence, newly formed string is 'bbbbbbbbbbbbbbbbbbbbbbbbbb'

And the largest prefix which is also suffix of string is 'bbbbbbbbbbbbbbbbbbbbbbbbb'

Time Limit: 3.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: 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, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications