Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×

jrrain's blog

Find most frequent word in stream of k words
By jrrain, history, 7 years ago, In English

I was solving this. My approach uses a queue to store k elements.A map and set are are also used in order to get most frequent lexicographically smallest string. But if I am using set to find lexicographically smallest frequent string it is getting tle. Please suggest some optimisations!.Here's my code

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

In most cases such complexity is efficient. Try to switch to unordered map,set. Also for faster io speed use ios_base::sync_with_stdio(false);

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You can improve the complexity by storing a set of strings for each frequency. When you modify the count of a certain word you can move it into the appropriate set. Then you can just read the string at the start of the set of the maximum count which you are maintaining.

Also to improve your speed 1. use stdio (scanf/printf) when there are long strings or even getchar 2. once you read in a string cache it using map to an integer so you can avoid passing around heavy strings and just use integers.

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

    Thanks @gongy here's my code with same approach giving WA. Could you please identify where I am getting wrong.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Line 27/28 don't make sense. If the current most frequent string is equal to the one you are decrementing, it doesn't necessarily decrease the maximum frequency, because there could be another string with that frequency.

      → Reply