Printing words starting with a given letter with the least amount of appearances with the print itself being an another appearance
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:


Remove the first word $w^*$ from $L_\ell$ and output it.
Insert $w^*$ into $R_\ell$.
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).
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$.