fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class StringQueries {
  5.     public static void main(String args[])throws Exception {
  6.         Reader re = new Reader(System.in);
  7.         int N = re.nextInt();
  8.         int Q = re.nextInt();
  9.         String S = re.next();
  10.  
  11.         int pre[][] = new int[26][N+1];
  12.         for(int i=0; i<26; i++){
  13.             pre[i][0] = 0;
  14.             for(int j=0; j<N; j++){
  15.                 pre[i][j+1] = pre[i][j];
  16.                 if(S.charAt(j)=='a'+i)
  17.                     pre[i][j+1]++;
  18.             }
  19.         }
  20.  
  21.         while(Q-->0){
  22.             int L = re.nextInt();
  23.             int R = re.nextInt();
  24.             int f[] = new int[26];
  25.             for(int i=0; i<26; i++)
  26.                 f[i] = pre[i][R]-pre[i][L-1];
  27.  
  28.             int m = (int)1e6;
  29.             for(int i=0; i<26; i++){
  30.                 int d = 0, k = f[i];
  31.                 for(int j=0; j<26; j++){
  32.                     if(f[j]<f[i])
  33.                         d += f[j];
  34.                     else
  35.                         d += f[j]-k;
  36.                 }
  37.                 m = Math.min(m, d);
  38.             }
  39.  
  40.             System.out.println(m);
  41.         }
  42.     }
  43. }
  44.  
  45.  
  46. class Reader{
  47.     BufferedReader br;
  48.     String words[];
  49.     int p;
  50.     Reader(InputStream in){
  51.         br = new BufferedReader(new InputStreamReader(in));
  52.         words = new String[]{};
  53.         p = 0;
  54.     }
  55.  
  56.     void ensureInput() throws Exception{
  57.         while(p==words.length){
  58.             words = br.readLine().split("\\s+");
  59.             p = 0;
  60.         }
  61.     }
  62.  
  63.     String next() throws Exception{
  64.         ensureInput();
  65.         return words[p++];
  66.     }
  67.  
  68.     int nextInt() throws Exception{
  69.         return Integer.parseInt(next());
  70.     }
  71. }
Success #stdin #stdout 0.04s 711168KB
comments (?)
stdin
copy 
8 2
abcdabcd
1 6
2 7
stdout
copy 
2
2
https://ideone.com/VvjUg3
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!