На вход поступает строка из строчных латинских букв(до 50000 символов), количество подстрок(до 50000), а далее пары чисел, обозначающих первый и последний элемент подстроки.
Пример:
abacaba
3
1 1
1 7
2 4
На выходе получить наиболее часто встречающийся элемент в каждой подстроке:
a
a
c
Задание сдается на автоматическое тестирование на сайте. Ограничение по времени 3 сек, по памяти 512 Мбайт. На одном из тестов выдает 3.11/3 сек, тест с максимальными входными данными. Назрел только один вопрос: как можно ускорить алгоритм? По памяти вроде с большим запасом проходит, да и результат верный выдает.
public class TheMostFrequentSymbol {
public static void main(String[] args) {
FastScanner in = new FastScanner(System.in);
PrintWriter out = new PrintWriter(System.out);
String s;
s = in.next();
int q;
q = in.nextInt();
int[] l = new int[q];
int[] r = new int[q];
for (int i = 0; i < q; ++i) {
l[i] = in.nextInt();
r[i] = in.nextInt();
}
char[] result = new char[q];
for (int k = 0; k < q; k++) {
Map<Character, Integer> map = new HashMap<>();
int max = 0;
for (int i = l[k] - 1; i < r[k]; i++) {
char ch = s.charAt(i);
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 1);
}
if (map.get(ch) >= max) {
max = map.get(ch);
result[k] = ch;
}
}
}
for (int i = 0; i < result.length; ++i) {
out.println(result[i]);
}
out.close();
}
static class FastScanner {
BufferedReader br;
StringTokenizer st;
FastScanner(InputStream stream) {
try {
br = new BufferedReader(new InputStreamReader(stream));
} catch (Exception e) {
e.printStackTrace();
}
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
- задание с coursera.org, для самообучения