fork(1) download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4.  
  5. /**
  6.  * created by asheshvidyut on 04/05/18
  7.  **/
  8. class Candies {
  9.     public static void main(String args[]) {
  10.         try {
  11.             InputReader in = new InputReader(System.in);
  12.             BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
  13.             char s[] = in.readLine().trim().toCharArray();
  14.             int freq[][] = new int[s.length][26];
  15.             for (int i = 0; i < s.length; i++) {
  16.                 if (i - 1 >= 0) {
  17.                     for (int j = 0; j < 26; j++) {
  18.                         freq[i][j] += freq[i - 1][j];
  19.                     }
  20.                 }
  21.                 freq[i][s[i] - 'a']++;
  22.             }
  23.             int tc = in.readInt();
  24.             for (int t = 0; t < tc; t++) {
  25.                 int n = in.readInt();
  26.                 int ans = Integer.MAX_VALUE;
  27.                 int low = n;
  28.                 int high = s.length;
  29.                 while(low <= high) {
  30.                     int mid = (low + high) >> 1;
  31.                     for (int i = 0; i < s.length; i++) {
  32.                         int next = i + mid - 1;
  33.                         if (next < s.length && next >= 0) {
  34.                             int f[] = new int[26];
  35.                             for (int j = 0; j < 26; j++) {
  36.                                 f[j] = freq[next][j];
  37.                                 if (i - 1 >= 0) {
  38.                                     f[j] -= freq[i - 1][j];
  39.                                 }
  40.                             }
  41.                             int countLetters = 0;
  42.                             Vector<Integer> odd = new Vector<>();
  43.                             for (int j = 0; j < 26; j++) {
  44.                                 if (f[j] % 2 != 0){
  45.                                     odd.add(f[j]);
  46.                                 }
  47.                                 else {
  48.                                     countLetters += f[j];
  49.                                 }
  50.                             }
  51.                             if (odd.size() == 0 && countLetters >= n) {
  52.                                 ans = Math.min(mid, ans);
  53.                             }
  54.                             else {
  55.                                 Collections.sort(odd);
  56.                                 for (int j = 0; j < odd.size() - 1; j++) {
  57.                                     countLetters += odd.get(j) - 1;
  58.                                 }
  59.                                 countLetters += odd.get(odd.size() - 1);
  60.                                 if (countLetters >= n) {
  61.                                     ans = Math.min(mid, ans);
  62.                                 }
  63.                             }
  64.                         }
  65.                     }
  66.                     if (ans == mid) {
  67.                         high = mid - 1;
  68.                     }
  69.                     else {
  70.                         low = mid + 1;
  71.                     }
  72.                     if (ans == n) {
  73.                         break;
  74.                     }
  75.                 }
  76.                 if (ans == Integer.MAX_VALUE)
  77.                     ans = -1;
  78.                 out.write(Integer.toString(ans));
  79.                 out.newLine();
  80.             }
  81.             out.close();
  82.         } catch (Exception e) {
  83.             e.printStackTrace();
  84.         }
  85.     }
  86. }
  87.  
  88.  
  89. class InputReader {
  90.     private boolean finished = false;
  91.  
  92.     private InputStream stream;
  93.     private byte[] buf = new byte[1024];
  94.     private int curChar;
  95.     private int numChars;
  96.  
  97.     public InputReader(InputStream stream) {
  98.         this.stream = stream;
  99.     }
  100.  
  101.     public int read() {
  102.         if (numChars == -1)
  103.             throw new InputMismatchException();
  104.         if (curChar >= numChars) {
  105.             curChar = 0;
  106.             try {
  107.                 numChars = stream.read(buf);
  108.             } catch (IOException e) {
  109.                 throw new InputMismatchException();
  110.             }
  111.             if (numChars <= 0)
  112.                 return -1;
  113.         }
  114.         return buf[curChar++];
  115.     }
  116.  
  117.     public int peek() {
  118.         if (numChars == -1)
  119.             return -1;
  120.         if (curChar >= numChars) {
  121.             curChar = 0;
  122.             try {
  123.                 numChars = stream.read(buf);
  124.             } catch (IOException e) {
  125.                 return -1;
  126.             }
  127.             if (numChars <= 0)
  128.                 return -1;
  129.         }
  130.         return buf[curChar];
  131.     }
  132.  
  133.     public int readInt() {
  134.         int c = read();
  135.         while (isSpaceChar(c))
  136.             c = read();
  137.         int sgn = 1;
  138.         if (c == '-') {
  139.             sgn = -1;
  140.             c = read();
  141.         }
  142.         int res = 0;
  143.         do {
  144.             if (c < '0' || c > '9')
  145.                 throw new InputMismatchException();
  146.             res *= 10;
  147.             res += c - '0';
  148.             c = read();
  149.         } while (!isSpaceChar(c));
  150.         return res * sgn;
  151.     }
  152.  
  153.     public long readLong() {
  154.         int c = read();
  155.         while (isSpaceChar(c))
  156.             c = read();
  157.         int sgn = 1;
  158.         if (c == '-') {
  159.             sgn = -1;
  160.             c = read();
  161.         }
  162.         long res = 0;
  163.         do {
  164.             if (c < '0' || c > '9')
  165.                 throw new InputMismatchException();
  166.             res *= 10;
  167.             res += c - '0';
  168.             c = read();
  169.         } while (!isSpaceChar(c));
  170.         return res * sgn;
  171.     }
  172.  
  173.     public String readString() {
  174.         int length = readInt();
  175.         if (length < 0)
  176.             return null;
  177.         byte[] bytes = new byte[length];
  178.         for (int i = 0; i < length; i++)
  179.             bytes[i] = (byte) read();
  180.         try {
  181.             return new String(bytes, "UTF-8");
  182.         } catch (UnsupportedEncodingException e) {
  183.             return new String(bytes);
  184.         }
  185.     }
  186.  
  187.     public static boolean isSpaceChar(int c) {
  188.         return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  189.     }
  190.  
  191.     private String readLine0() {
  192.         StringBuffer buf = new StringBuffer();
  193.         int c = read();
  194.         while (c != '\n' && c != -1) {
  195.             if (c != '\r')
  196.                 buf.appendCodePoint(c);
  197.             c = read();
  198.         }
  199.         return buf.toString();
  200.     }
  201.  
  202.     public String readLine() {
  203.         String s = readLine0();
  204.         while (s.trim().length() == 0)
  205.             s = readLine0();
  206.         return s;
  207.     }
  208.  
  209.     public String readLine(boolean ignoreEmptyLines) {
  210.         if (ignoreEmptyLines)
  211.             return readLine();
  212.         else
  213.             return readLine0();
  214.     }
  215.  
  216.     public BigInteger readBigInteger() {
  217.         try {
  218.             return new BigInteger(readString());
  219.         } catch (NumberFormatException e) {
  220.             throw new InputMismatchException();
  221.         }
  222.     }
  223.  
  224.     public char readCharacter() {
  225.         int c = read();
  226.         while (isSpaceChar(c))
  227.             c = read();
  228.         return (char) c;
  229.     }
  230.  
  231.     public double readDouble() {
  232.         int c = read();
  233.         while (isSpaceChar(c))
  234.             c = read();
  235.         int sgn = 1;
  236.         if (c == '-') {
  237.             sgn = -1;
  238.             c = read();
  239.         }
  240.         double res = 0;
  241.         while (!isSpaceChar(c) && c != '.') {
  242.             if (c == 'e' || c == 'E')
  243.                 return res * Math.pow(10, readInt());
  244.             if (c < '0' || c > '9')
  245.                 throw new InputMismatchException();
  246.             res *= 10;
  247.             res += c - '0';
  248.             c = read();
  249.         }
  250.         if (c == '.') {
  251.             c = read();
  252.             double m = 1;
  253.             while (!isSpaceChar(c)) {
  254.                 if (c == 'e' || c == 'E')
  255.                     return res * Math.pow(10, readInt());
  256.                 if (c < '0' || c > '9')
  257.                     throw new InputMismatchException();
  258.                 m /= 10;
  259.                 res += (c - '0') * m;
  260.                 c = read();
  261.             }
  262.         }
  263.         return res * sgn;
  264.     }
  265.  
  266.     public boolean isExhausted() {
  267.         int value;
  268.         while (isSpaceChar(value = peek()) && value != -1)
  269.             read();
  270.         return value == -1;
  271.     }
  272.  
  273.     public String next() {
  274.         return readString();
  275.     }
  276.  
  277.     public boolean readBoolean() {
  278.         return readInt() == 1;
  279.     }
  280. }
Success #stdin #stdout #stderr 0.09s 27828KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
java.util.InputMismatchException
	at InputReader.read(Main.java:103)
	at InputReader.readLine0(Main.java:193)
	at InputReader.readLine(Main.java:205)
	at Candies.main(Main.java:13)
https://ideone.com/uhSNlG
language:
Java (HotSpot 12)
created:
5 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!