In this HackerEarth String Queries problem solution 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 ?


HackerEarth String Queries problem solution


HackerEarth String Queries problem solution.

import java.io.*;
import java.util.*;
public final class string_queries
{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static FastScanner sc=new FastScanner(br);
static PrintWriter out=new PrintWriter(System.out);
static Random rnd=new Random();
static int[][] pre;
static int[] sum=new int[26];

public static void main(String args[]) throws Exception
{
int n=sc.nextInt(),q=sc.nextInt();char[] a=sc.next().toCharArray();pre=new int[26][n];
for(int i=0;i<n;i++)
{
sum[a[i]-'a']++;
for(int j=0;j<26;j++)
{
pre[j][i]=sum[j];
}
}
for(int i=0;i<q;i++)
{
int l=sc.nextInt()-1,r=sc.nextInt()-1;int[] cnt=new int[26];
for(int j=0;j<26;j++)
{
cnt[j]=(pre[j][r]-(l==0?0:pre[j][l-1]));
}
List<Integer> list=new ArrayList<Integer>();int sum=0;
for(int j=0;j<26;j++)
{
if(cnt[j]>0)
{
list.add(cnt[j]);sum+=cnt[j];
}
}
int now=0,ans=Integer.MAX_VALUE;Collections.sort(list);
for(int j=0;j<list.size();j++)
{
int curr1=now,curr2=sum-now,curr3=curr2-(list.get(j)*(list.size()-j));
now+=list.get(j);ans=Math.min(ans,curr1+curr3);
}
out.println(ans);
}
out.close();
}
}
class FastScanner
{
BufferedReader in;
StringTokenizer st;

public FastScanner(BufferedReader in) {
this.in = in;
}

public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return st.nextToken();
}

public String next() throws Exception {
return nextToken().toString();
}

public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}

public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}

public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}