sidchintamaneni's blog

(Equal Frequancy) in Hacker rank Hack the Interview VII
By sidchintamaneni, history, 4 years ago, In English

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)

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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)

        → Reply