All Tracks Algorithms String Algorithms Basics of String Manipulation Problem

String Queries

Data Structures, Easy-Medium, String Algorithms, approved


Given a 1-indexed String S of length N, consisting of lowercase English alphabets, you need to answer queries based on the properties of this string.

You shall be given Q queries to answer. In each query you shall be given 2 integers L and R. Now , you need to report the minimum number of String elements you need to delete in the substring of String S ranging from L to R inclusive, so that each distinct character occurring in the range occurs equal number of times.

For example, consider the String \("abcdab"\) . Here, the characters occurring in this String are a. b, c and d. On deleting one occurrence of a as well as b one of the possible Strings is \(abcd\). Each character occuring in the range now occurs equal number of times. So, the minimum number of deletions is two.

Note that we need to equalize the count of only characters that occur in the range, and not of characters that do not. It is allowed to delete all occurences of a character, so that it no longer occurs in the range at all

Can you do it ?

Input Format :

The first line contains 2 space separated integers N and Q. The next line contains the String S. Each of the next Q lines contains 2 space separated integers L and R, denoting the parameters of the \(i^{th}\) query.

Output Format :

Print the answer to each query on a new line.

Constraints :

\( 1 \le N, Q \le 10^5 \)

\( 1 \le L \le R \le N \)

8 2
1 6
2 7

The explanation to the \(1^{st}\) query in the sample has been provided in the problem statement. For the \(2^{nd}\) query, the substring required here is \("bcdabc"\) . We can delete from this substring one occurence one occurence of b and c to achieve the desired result. Thus, the answer is 2.

Time Limit: 2.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, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in

Capillary Technologies

Challenge Name

Capillary Java Developers Challenge

View All Notifications