0
$\begingroup$

I've had problems with this one and was unable to solve it on my Algorithms 1 exam:

Input: -n words -k letters

Problem: For each letter print out the one word which starts with that letter and has the least number of appearances. If there are more than one, write the lexicographically smallest one. The printing of a word counts as an appearance.

Complexity: Time: O (nlogn + k) Space: O ( n + k )

This is the first algorithm I am unable to solve in given time complexity and it is driving me crazy.

Appreciate the help!

Example:

n=6 words: dog bark dog woof doggy doggy

k=2 letters and corresponding outputs: d - 2 is the least number of appearances of a word starting with d , dog and doggy - dog is the lexicographically smaller one so we print dog

if we say d again, since we printed out dog, that counts as another appearance so the only word appearing twice is doggy, and we print that one

$\endgroup$
  • $\begingroup$ It would be better if you can give one example to understand what you intend with your statements. $\endgroup$ – Navjot Waraich Jun 28 at 12:00
  • 1
    $\begingroup$ Perhaps you could choose a more specific title. $\endgroup$ – Yuval Filmus Jun 28 at 15:13
  • 1
    $\begingroup$ @NavjotWaraich I've updated the question $\endgroup$ – Dragan Bjekic Jun 28 at 15:46
0
$\begingroup$

The following assumes that you can store words in $O(1)$ space and compare them in $O(1)$ time.

For each letter $\ell$ keep:

  • The number of appearances $n_\ell$ of the word starting with $\ell$ that appears the least amount of times.

  • A list $L_\ell$ of words starting with $\ell$ that appeared $n_\ell$ times, in lexicographic order.

  • A list $R_\ell$ of words starting with $\ell$ that appeared $n_\ell + 1$ times and are smaller than the first word in $L_\ell$, in lexicographic order.

  • A sorted list $S_\ell$ of pairs $(n_w, w)$, where $w$ is a word starting with $\ell$ that appears $n_w \ge n_\ell+1$ times and is not in $R_\ell$. The pairs are sorted in lexicographic order.

Notice that you can construct everything above in $O(n \log n)$ overall time for all the letters $\ell$.

When you have to return a word starting with letter $\ell$, do the following:

  1. Remove the first word $w^*$ from $L_\ell$ and output it.
  2. Insert $w^*$ into $R_\ell$.
  3. Insert all the words $w$ from a pair $(n_w, w)$ of $S_\ell$ such that (i) $n_w = n_\ell + 1$, and (ii) $w$ precedes the smallest word of $L_\ell$, into $R_\ell$. Delete the corresponding pairs from $S_\ell$. Notice that these are always the first elements in $S_\ell$. If $L_\ell$ is empty, then ignore constraint (ii).

  4. If $L_\ell$ is empty, increase $n_\ell$ by 1, swap $R_\ell$ and $L_\ell$, and repeat step 3.

Steps 1, 2, and 4 can be performed in constant time. Step 3 requires a constant amount of time, plus a time proportional to the number of words $w$ moved from $S_\ell$ into $R_\ell$. This second term is upper bounded by $O(n)$ across all letters as this is an upper bound on the number of pairs contained in all $S_\ell$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.