Блог пользователя sidchintamaneni

(Equal Frequancy) in Hacker rank Hack the Interview VII
Автор sidchintamaneni, история, 4 года назад, По-английски

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)

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

        → Ответить