Finding the length of the longest substring with equal frequency of characters. for example: input : aaaabbb output: 6 (aaabbb) input: abbacdef output: 6 (bacdef) can anyone help me out with any hints or ideas you got?? (Thanks in advance)
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 3 | cry | 159 |
| 5 | atcoder_official | 158 |
| 5 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 149 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.09.2024 16:31:07 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Binary search on answers For each mid calculate if there is any substring of length mid that have equal frequency of character (can be done in O(n*26) Total time complexity nlogn approx
binary search doesn't work...it's not like if there's an equal frequency substring of length mid, there would always be an equal frequency substring of length mid-1.
Is there only a O(n^2) brute force with prefix sum possible, or do you know of something better of the top of your head?
Try to exploit the fact that if there's such a substring from L to R, the difference arrays of prefix frequency array at (L-1) and R would be same.You could reduce it to O(26 * N * LogN).
(LogN is due to the map)