Toys
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: greedy, strings

Vittorio has three favorite toys: a teddy bear, an owl, and a raccoon. Each of them has a name.

Vittorio takes several sheets of paper and writes a letter on each side of every sheet so that it is possible to spell any of the three names by arranging some of the sheets in a row (sheets can be reordered and flipped as needed). The three names do not have to be spelled at the same time, it is sufficient that it is possible to spell each of them using all the available sheets (and the same sheet can be used to spell different names).

Find the minimum number of sheets required. In addition, produce a list of sheets with minimum cardinality which can be used to spell the three names (if there are multiple answers, print any).

Input format:
The first line contains a string $$$t$$$ consisting of uppercase letters of the English alphabet ($$$1\le |t| \le 1000$$$) — the name of the teddy bear.

The second line contains a string $$$o$$$ consisting of uppercase letters of the English alphabet ($$$1\le |o| \le 1000$$$) — the name of the owl.

The third line contains a string $$$r$$$ consisting of uppercase letters of the English alphabet ($$$1\le |r| \le 1000$$$) — the name of the raccoon.

The values $$$|t|$$$, $$$|o|$$$, $$$|r|$$$ denote the length of the three names $$$t$$$, $$$o$$$, $$$r$$$.

Output format:
The first line of the output contains a single integer $$$m$$$ — the minimum number of sheets required.

Then $$$m$$$ lines follow: the $$$j$$$-th of these lines contains a string of two uppercase letters of the English alphabet — the letters appearing on the two sides of the $$$j$$$-th sheet.

Note that you can print the sheets and the two letters of each sheet in any order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the solution uses two sheets: the first sheet has A on one side and G on the other side; the second sheet has A on one side and M on the other side.

The name AA can be spelled using the A side of both sheets. The name GA can be spelled using the G side of the first sheet and the A side of the second sheet. Finally, the name MA can be spelled using the M side of the second sheet and the A side of the first sheet.

Example input:
AA
GA
MA

Example output:
2
AG
AM

Example input:
TEDDY
HEDWIG
RACCOON

Example output:
8
AT
CH
CY
DG
DO
ER
IN
OW

Editorial:
Toys is one of the most challenging problems of the contest, but no particular knowledge of algorithms and data structures is required to solve it. We propose two greedy solutions that start with a common reformulation of the problem statement. The limit to the length of the three names is very permissive ($$$\leq 1000$$$), so there is no need to pay much attention to computational efficiency.
Problem reformulation and notations
Suppose to have a set of sheets that allows to spell all three names. Once we fix the way all names are spelled, each sheet either contributes to the $$$i$$$-th name with a letter $$$x_i$$$ or does not contribute to the $$$i$$$-th name. In the latter case, we conventionally set $$$x_i = \star$$$. The triplet $$$(x_1, \, x_2, \, x_3)$$$ consists of three English letters ($$$\texttt{A}$$$-$$$\texttt{Z}$$$) or $$$\star$$$, with the constraint that at most two different English letters can occur (we say that such a triplet is valid).
The problem can then be reformulated as follows: find a set of valid triplets $$$(x_1^1, \, x_2^1, \, x_3^1), \, \dots,$$$ $$$(x_1^m, \, x_2^m, \, x_3^m)$$$ of minimal size $$$m$$$ such that, for each $$$i \in \{1, \, 2, \, 3\}$$$, the letters $$$x_i^1, \, \dots, \, x_i^m$$$ are a permutation of the $$$i$$$-th name with some extra $$$\star$$$'s. A set of valid triplets satisfying this property (not necessarily of minimal size) will be called an admissible set; if it is also of minimal size, it will be called an optimal admissible set.
For instance, in the first sample, the two sheets $$$\texttt{AG}$$$ and $$$\texttt{AM}$$$ can be represented by the triples $$$(\texttt{A}, \, \texttt{G}, \, \texttt{A})$$$ and $$$(\texttt{A}, \, \texttt{A}, \, \texttt{M})$$$ to form the three names $$$\texttt{AA}$$$, $$$\texttt{GA}$$$, $$$\texttt{MA}$$$. In the second sample (where the three names are $$$\texttt{TEDDY}$$$, $$$\texttt{HEDWIG}$$$, and $$$\texttt{RACCOON}$$$), the eight sheets of the sample output can be represented by the triplets in the following columns:
Denote by $$$f_i(x)$$$ the number of occurrences of the letter $$$x$$$ in the $$$i$$$-th name. Let $$$f(x) =$$$ $$$(f_1(x),$$$ $$$f_2(x),$$$ $$$f_3(x))$$$. For instance, in the second sample, $$$f(\texttt{D}) = (2, \, 1, \, 0)$$$. Denote by $$$l_1, \, l_2, \, l_3$$$ the lengths of the three names.
Comments on the sample inputs/outputs
The first sample (where the three input names are $$$\texttt{AA}$$$, $$$\texttt{GA}$$$, $$$\texttt{MA}$$$) is very small but it already shows that one can cleverly construct a solution with only two sheets, by putting the $$$\texttt{G}$$$ and the $$$\texttt{M}$$$ in two different sheets. If we are not careful and put the $$$\texttt{G}$$$ and the $$$\texttt{M}$$$ on the two sides of the same sheet, then we are forced to use a total of three sheets which is sub-optimal. Note that $$$\texttt{AA}$$$, $$$\texttt{GA}$$$, and $$$\texttt{MA}$$$ are indeed among Vittorio's early favorite words.
A trivial lower bound to the number of sheets needed is $$$\max(l_1, \, l_2, \, l_3)$$$. The second sample ($$$\texttt{TEDDY}$$$, $$$\texttt{HEDWIG}$$$, $$$\texttt{RACCOON}$$$) is a case where $$$\max(l_1, \, l_2, \, l_3) = 7$$$ sheets are not enough. To become convinced that this is indeed the case, one can try to construct an admissible set of $$$7$$$ triplets having the letters of $$$\texttt{RACCOON}$$$ in the third positions. None of the letters of $$$\texttt{RACCOON}$$$ is reusable in the other two names, so the only way to save some space is to have two $$$\texttt{D}$$$'s on one sheet and two $$$\texttt{E}$$$'s on another sheet (these are the letters in common between $$$\texttt{TEDDY}$$$ and $$$\texttt{HEDWIG}$$$). Since $$$l_1 + l_2 = 11$$$, we would still need $$$9$$$ sheets. If we try instead to construct $$$8$$$ sheets, one of them is not required to spell $$$\texttt{RACCOON}$$$ (so the corresponding triplet has a $$$\star$$$ in the third position) and so it can fit two different letters from $$$\texttt{TEDDY}$$$ and $$$\texttt{HEDWIG}$$$ (for instance, $$$\texttt{D}$$$ and $$$\texttt{G}$$$ in the sample output).
At this point, one could guess that the minimal number of sheets is given by the formula $$$$$$  \max\left(l_1, \, l_2, \, l_3, \, \left\lceil \frac{1}{2} \sum_x \max f(x) \right\rceil \right). $$$$$$ Indeed, each of the four terms inside the $$$\max$$$ is a lower bound to the minimal number of sheets: this is clear for $$$l_1, \, l_2, \, l_3$$$; the summation in the fourth term is a lower bound on the number of letters that need to be written on all the sheets, and each sheet has space for two letters, hence the $$$\frac{1}{2}$$$ factor. However, it turns out that this lower bound might not be attained. In fact, in the third sample ($$$\texttt{BDC}$$$, $$$\texttt{CAA}$$$, $$$\texttt{CE}$$$), the lower bound is $$$\max(3, \, 3, \, 2, \, 3) = 3$$$ but at least $$$4$$$ sheets are needed.
First solution
We start with the following observation. It is relatively simple, but it will turn out to be very useful.
Lemma 1. If $$$f_1(x) \geq f_2(x) \geq f_3(x)$$$ and $$$f_1(x), \, f_2(x) > 0$$$, then there exists an optimal admissible set that includes a triplet of the form $$$(x, \, x, \, y)$$$ for some $$$y$$$.
Proof. Suppose to have an optimal admissible set where no triplet has the form $$$(x, \, x, \, y)$$$. There is at least one triplet $$$s_1 = (x, \, y, \, y')$$$ where $$$x$$$ appears in first position (but not in second) and at least one triplet $$$s_2 = (z, \, x, \, z')$$$ where $$$x$$$ appears in second position (but not in first). If $$$s_1$$$ can be chosen so that $$$y, \, y' \neq x$$$, then we can replace $$$s_1$$$ and $$$s_2$$$ with the valid triplets $$$(x, \, x, \, z')$$$, $$$(z, \, y, \, y')$$$. If $$$s_2$$$ can be chosen so that $$$z, \, z' \neq x$$$, then we can replace $$$s_1$$$ and $$$s_2$$$ with the valid triplets $$$(x, \, x, \, y')$$$, $$$(z, \, y, \, z')$$$. If none of the previous cases occurs, all triplets containing $$$x$$$ are of the form $$$(t, \, t', \, x)$$$. Therefore, $$$f_3(x) \geq f_1(x), \, f_2(x)$$$. This implies that $$$f_1(x) = f_2(x) = f_3(x)$$$, so all triplets containing $$$x$$$ are equal to $$$(x, \, x, \, x)$$$. $$$\blacksquare$$$
We now describe the first and most important step in our solution. As long as the hypothesis of Lemma 1 holds for some letter $$$x$$$ with $$$f_1(x) + f_2(x) + f_3(x) \geq 3$$$, replace one occurrence of the letter $$$x$$$ in the first and second name with a new letter $$$x'$$$ (not appearing in any of the three names and not necessarily belonging to the English alphabet). This operation does not decrease the minimal number of triplets needed: any set that is admissible for the three new names is also admissible for the old names, after replacing $$$x'$$$ with $$$x$$$. Thanks to Lemma 1, the minimal number of triplets needed remains the same.
When the hypothesis of Lemma 1 does not hold anymore (even after reordering the three names), each letter appears either in at most one name (possibly several times) or exactly twice across all three names. For each letter $$$x$$$ that appears in only one name (say, $$$k$$$ times), replace all occurrences of $$$x$$$ with different new letters $$$x_1, \, \dots, \, x_k$$$. This does not impact the optimal size of an admissible set, because all occurrences of $$$x$$$ necessarily appear in different triplets. After this operation, every letter appears at most once in each name and at most twice across all three names.
For instance, the three names of the second sample could become as follows (we create new letters by adding subscripts to standard English letters): $$$\texttt{T}_1\texttt{E}_1\texttt{D}_1\texttt{D}_2\texttt{Y}_1$$$, $$$\texttt{H}_1\texttt{E}_1\texttt{D}_1\texttt{W}_1\texttt{I}_1\texttt{G}_1$$$, $$$\texttt{R}_1\texttt{A}_1\texttt{C}_1\texttt{C}_2\texttt{O}_1\texttt{O}_2\texttt{N}_1$$$. We say that a letter is double if it appears twice across the three names (such as $$$\texttt{D}_1$$$ in the previous example) and single if it appears once (such as $$$\texttt{D}_2$$$).
After changing the three names as described above, our greedy solution is as follows.
1. As long as there are a double letter $$$x$$$ and a single letter $$$y$$$ that appear in different names (assume without loss of generality that $$$x$$$ appears in the first two names and $$$y$$$ appears in the third), create a valid triplet $$$(x, \, x, \, y)$$$ and erase the occurrences of $$$x$$$ and $$$y$$$ from the three names.
2. As long as there are three double letters $$$x, \, y, \, z$$$ with $$$f(x) = (1, \, 1, \, 0)$$$, $$$f(y) = (0, \, 1, \, 1)$$$, and $$$f(z) = (1, \, 0, \, 1)$$$, create the two valid triplets $$$(x, \, x, \, z)$$$ and $$$(z, \, y, \, y)$$$, then erase all occurrences of $$$x, \, y, \, z$$$ from the three names.
3. As long as there is a double letter $$$x$$$ (assume without loss of generality that it appears in the first two names), create a valid triplet $$$(x, \, x, \, \star)$$$ and erase the two occurrences of $$$x$$$ in the first two names.
4. As long as at least two names are non-empty, take letters $$$x, \, y$$$ from the two longest names (assume without loss of generality that they are the first and the second name), create a valid triplet $$$(x, \, y, \, \star)$$$, and erase the occurrences of $$$x$$$ and $$$y$$$.
5. As long as exactly one of the names is non-empty (assume without loss of generality that it is the first), create a triplet $$$(x, \, \star, \, \star)$$$ using a letter $$$x$$$ of the first name and erase $$$x$$$ from the first name.
The following lemmas show that the solution we have just described leads to an optimal set of triplets.
Lemma 2. Suppose that $$$x$$$ is a double letter and $$$y$$$ is a single letter with $$$f(x) = (1, \, 1, \, 0)$$$ and $$$f(y) = (0, \, 0, \, 1)$$$. Then there exists an optimal admissible set that includes the triplet $$$(x, \, x, \, y)$$$.
Proof. An optimal admissible set necessarily contains one triplet of the form $$$(z, \, z', \, y)$$$ with $$$z, \, z' \neq y$$$. We can swap $$$z$$$ with the only occurrence of $$$x$$$ in the first position of some triplet and $$$z'$$$ with the only occurrence of $$$x$$$ in the second position of some triplet. All triplets remain valid after this operation. $$$\blacksquare$$$
Lemma 3. Suppose that the hypothesis of Lemma 2 does not apply. If $$$x, \, y, \, z$$$ are double letters with $$$f(x) = (1, \, 1, \, 0)$$$, $$$f(y) = (0, \, 1, \, 1)$$$, and $$$f(z) = (1, \, 0, \, 1)$$$, then there is an optimal admissible set that includes the triplets $$$(x, \, x, \, z)$$$ and $$$(z, \, y, \, y)$$$.
Proof. An optimal admissible set necessarily contains one triplet of the form $$$(x, \, x, \, z')$$$. Since there are no single letters (otherwise, the hypothesis of Lemma 2 would hold), $$$z'$$$ is a double letter, so the solution also contains a valid triplet $$$(z', \, y', \, y")$$$ or $$$(y', \, z', \, y")$$$ with $$$y', \, y" \neq z'$$$. In the first case, swap the two occurrences of $$$z'$$$ with the two occurrences of $$$z$$$; then swap $$$y'$$$ with one occurrence of $$$y$$$ and $$$y"$$$ with the other occurrence of $$$y$$$. We obtain the valid triplets $$$(x, \, x, \, z)$$$ and $$$(z, \, y, \, y)$$$, as desired. In the second case, we can similarly obtain $$$(x, \, x, \, y)$$$ and $$$(z, \, y, \, z)$$$. One additional swap of $$$y$$$ and $$$z$$$ in the third position leads to $$$(x, \, x, \, z)$$$ and $$$(z, \, y, \, y)$$$. $$$\blacksquare$$$
Lemma 4. Suppose that the hypotheses of Lemmas 2 and 3 do not apply. If $$$x$$$ is a double letter with $$$f(x) = (1, \, 1, \, 0)$$$, then there is an optimal admissible set that includes the triplet $$$(x, \, x, \, \star)$$$.
Proof. Among all optimal admissible sets, choose one which maximizes the number of triplets with two equal letters $$$\neq \star$$$. The chosen set necessarily includes a triplet of the form $$$(x, \, x, \, y)$$$ with $$$y \neq x$$$. We are going to prove that $$$y = \star$$$ (using the maximality assumption). Suppose by contradiction that $$$y \neq \star$$$. Then $$$y$$$ is a double letter, otherwise, Lemma 2 would apply. Therefore, the set includes a valid triplet of the form $$$(y, \, z, \, z')$$$ or $$$(z, \, y, \, z')$$$, for some $$$z, \, z' \neq y$$$; without loss of generality, assume that the first case occurs. If $$$z = z'$$$ is a double letter, then Lemma 3 applies, which is a contradiction. This means that at least one of $$$z$$$ and $$$z'$$$ is $$$\star$$$. We can then swap the $$$y$$$ and the $$$z'$$$ in the third positions, obtaining the valid triplets $$$(x, \, x, \, z')$$$ and $$$(y, \, z, \, y)$$$. This increases by $$$1$$$ the number of triplets with two equal letters, violating the maximality assumption. $$$\blacksquare$$$
Lemma 5. Suppose that there are single letters only. If the lengths of the three names satisfy $$$l_1 \geq l_2 \geq l_3$$$ and $$$l_1, \, l_2 > 0$$$, then there is an optimal admissible set that includes a triplet $$$(x, \, y, \, \star)$$$ where $$$x$$$ is any (single) letter of the first name and $$$y$$$ is any (single) letter of the second name.
Proof. Suppose by contradiction to have an optimal set with no triplets of the form $$$(x, \, y, \, \star)$$$. For $$$i \in \{1, \, 2, \, 3\}$$$ denote by $$$t_i$$$ the number of triplets with one single letter at position $$$i$$$ and two $$$\star$$$; for $$$1 \leq i < j \leq 3$$$, denote by $$$t_{i,j}$$$ the number of triplets with single letters at positions $$$i$$$ and $$$j$$$. At most one of $$$t_1, \, t_2, \, t_3$$$ is non-zero, otherwise, we could merge two triplets into one, which goes against the optimality assumption. In addition, $$$t_{1,2} = 0$$$. By counting the letters occurring in each position of the triplets, we easily get $$$l_1 = t_1 + t_{1,3}$$$, $$$l_2 = t_2 + t_{2,3}$$$, and $$$l_3 = t_3 + t_{1,3} + t_{2,3}$$$. Since at least one of $$$t_1$$$ and $$$t_2$$$ is zero, we have that $$$l_3 \geq \min(l_1, \, l_2)$$$, so $$$l_2 = l_3$$$. This forces $$$t_3 = 0$$$ and $$$t_2 = t_{1,3}$$$. If $$$t_2 = t_{1,3} > 0$$$, then there is at least one triplet of the form $$$(x, \, \star, \, z)$$$ and one the form $$$(\star, \, y, \, \star)$$$; we can swap $$$x$$$ and $$$\star$$$ the first positions to obtain $$$(x, \, y, \, \star)$$$ and $$$(\star, \, \star, \, z)$$$, as desired. Otherwise, $$$t_2 = t_{1,3} = 0$$$, so $$$t_1 \geq t_{2,3} > 0$$$ and we conclude in a similar way by transforming two triplets of the form $$$(x, \, \star, \, \star)$$$ and $$$(\star, \, y, \, z)$$$ into $$$(x, \, y, \, \star)$$$ and $$$(\star, \, \star, \, z)$$$. $$$\blacksquare$$$
Second solution
The alternative solution we propose does not use the idea of changing the letters. Instead, the key greedy step is the following: as long as one name (say, the first) contains a letter $$$x$$$ with $$$f_1(x) > f_2(x) + f_3(x)$$$ and the other two names contain a common letter $$$y$$$ with $$$f_1(y) < f_2(y) + f_3(y)$$$, we create the triplet $$$(x, \, y, \, y)$$$ and decrease the length of the three names by $$$1$$$. The optimality of this step is proved in Lemma 8 below. Once this can no longer be done, we are left with four possible cases (described by Lemma 9 below) and we show how to conclude greedily in each case: one case is in common with the first solution; in the other three cases, there is an admissible set of size $$$\max(l_1, \, l_2, \, l_3)$$$ which is clearly optimal (since we need at least one triplet for each letter of the longest name).
Lemma 6. Suppose that $$$f_1(x) > f_2(x) + f_3(x)$$$ for some English letter $$$x$$$. Then any admissible set includes a triplet $$$(x, \, y, \, y')$$$ with $$$y, \, y' \neq x$$$, where $$$y$$$ and $$$y'$$$ can be either English letters or $$$\star$$$.
Proof. For all $$$i \in \{1, \, 2, \, 3\}$$$, any admissible set must have exactly $$$f_i(x)$$$ triplets with $$$x$$$ in the $$$i$$$-th position. Therefore, at least one triplet has $$$x$$$ in the first position but not in the second or third position. $$$\blacksquare$$$
Lemma 7. Suppose that $$$f_1(x) < f_2(x) + f_3(x)$$$, $$$f_2(x) > 0$$$, and $$$f_3(x) > 0$$$, for some English letter $$$x$$$. Then there is an optimal admissible set that includes a triplet $$$(y, \, x, \, x)$$$ where $$$y$$$ can be either an English letter or $$$\star$$$.
Proof. Fix an optimal admissible set. If at least one triplet has $$$x$$$ both in the second and third position, then we are done. Otherwise, the inequality $$$f_1(x) < f_2(x) + f_3(x)$$$ ensures that at least one triplet $$$s_1$$$ has $$$x$$$ in the second or third position but not in the first position. Suppose without loss of generality that $$$s_1 = (z, \, z', \, x)$$$ with $$$z, \, z' \neq x$$$. Since $$$f_2(x) > 0$$$, there exists at least one triplet $$$s_2$$$ of the form $$$(y, \, x, \, y')$$$. We can then replace the triplets $$$s_1$$$ and $$$s_2$$$ with the following two valid triplets: $$$(y, \, x, \, x)$$$ and $$$(z, \, z', \, y')$$$. $$$\blacksquare$$$
Lemma 8. Suppose that $$$f_1(x) > f_2(x) + f_3(x)$$$, $$$f_1(y) < f_2(y) + f_3(y)$$$, and $$$f_2(y), \, f_3(y) > 0$$$ for some English letters $$$x, \, y$$$. Then there is an optimal admissible set that includes a triplet $$$(x, \, y, \, y)$$$.
Proof. By Lemma 7, there exists an optimal admissible set that includes a triplet $$$s_1$$$ of the form $$$(z, \, y, \, y)$$$. If $$$z = x$$$, then we are done. Otherwise, by Lemma 6, the set also includes a triplet $$$s_2$$$ of the form $$$(x, \, t, \, t')$$$ with $$$t, \, t' \neq x$$$. We can then replace $$$s_1$$$ and $$$s_2$$$ with the following two valid triplets: $$$(x, \, y, \, y)$$$ and $$$(z, \, t, \, t')$$$. $$$\blacksquare$$$
Lemma 9. If the hypothesis of Lemma 8 does not apply, we are in at least one of the following cases:
1. For all letters $$$x$$$, the numbers $$$f_1(x), \, f_2(x), \, f_3(x)$$$ form the sides of a (possibly degenerate) triangle.
2. Up to changing the order of the three names, $$$f_1(x) \geq f_2(x) + f_3(x)$$$ for all letters $$$x$$$.
3. One of the names is empty.
4. The three names have disjoint letters.
Proof. We say that the first name is beautiful if $$$f_1(x) > f_2(x) + f_3(x)$$$ for at least one letter $$$x$$$, and we analogously define beauty for the second and third name.
• If none of the three names is beautiful, then we are in case (1).
• If exactly one name is beautiful (say, the first one), then $$$f_1(x) > f_2(x) + f_3(x)$$$ for some letter $$$x$$$; if $$$f_1(y) < f_2(y) + f_3(y)$$$ for some $$$y$$$, then $$$f_2(y), \, f_3(y) > 0$$$ (otherwise, the second or third name would be beautiful), so Lemma 8 applies, which is a contradiction. Therefore we are in case (2).
• If exactly two names are beautiful (say, the first and the second name), we are going to prove that the third name is empty, so we are in case (3).  Indeed, suppose by contradiction that the third name contains some letter $$$y$$$.  Then $$$f_3(y) \leq f_1(y) + f_2(y)$$$ because the third name is not beautiful, so at least one other name (say, the second) contains the letter $$$y$$$.  Since the first name is beautiful and Lemma 8 does not apply, we have $$$f_1(y) \geq f_2(y) + f_3(y)$$$ and in particular, the first name also contains the letter $$$y$$$.  Similarly, since the second name is beautiful and Lemma 8 does not apply (after swapping the first and second name), we get $$$f_2(y) \geq f_1(y) + f_3(y)$$$.  Combining the previous two inequalities, we get $$$f_1(y) \geq f_2(y) + f_3(y) \geq f_1(y) + 2 f_3(y)$$$, so $$$f_3(y) = 0$$$, a contradiction.
• Finally, if all three names are beautiful, we are going to prove that we are in case (4).  Indeed, suppose by contradiction that two names (say, the second and the third) have a letter $$$y$$$ in common.  Since the first name is beautiful and Lemma 8 does not apply, we have $$$f_1(y) \geq f_2(y) + f_3(y)$$$, so in particular the first name also contains $$$y$$$.  Since the second name is beautiful and Lemma 8 does not apply, we also have $$$f_2(y) \geq f_1(y) + f_3(y)$$$, which is a contradiction because $$$f_3(y) > 0$$$. $$$\blacksquare$$$
If we are in case (2), we easily conclude with $$$l_1$$$ additional triplets. If we are in case (3), assuming without loss of generality that the third name is empty, we conclude with additional $$$\max(l_1, \, l_2)$$$ triplets. Case (4) is handled as in Lemma 5 at the end of the first solution (we are left with single letters only).
Only case (1) remains, and we are going to show that in such case we can conclude with $$$\max(l_1, \, l_2, \, l_3)$$$ additional triplets. We say that the first and second names are friends if there is a letter $$$x$$$ such that $$$f_1(x), \, f_2(x) > 0$$$ and $$$f_1(x)-1, \, f_2(x)-1, \, f_3(x)$$$ form the sides of a triangle (we say that the letter $$$x$$$ proves the friendship between the first and second names). We define the friendship for the other two pairs of names analogously. Iteratively proceed as follows:
1. As long as there is a letter $$$x$$$ such that $$$f_1(x)-1, \, f_2(x)-1, \, f_3(x)-1$$$ form the sides of a triangle, we create a triplet $$$(x, \, x, \, x)$$$ and erase one occurrence of $$$x$$$ from each name.
2. As long as each name is a friend of the other two, then let $$$x, \, y, \, z$$$ be three letters that prove the friendships. We create two triplets $$$(x, \, x, \, y)$$$ and $$$(z, \, y, \, z)$$$, then erase $$$x$$$ and $$$z$$$ from the first name, $$$x$$$ and $$$y$$$ from the second name, $$$y$$$ and $$$z$$$ from the third name.
3. If we are not in case (1) or (2), suppose without loss of generality that the second and third names are not friends.  We are going to prove that $$$f_1(x) \geq f_2(x) + f_3(x)$$$ for all letters $$$x$$$, so we can conclude as in case (2).  If $$$f_2(x) = 0$$$, then $$$f_1(x) = f_3(x)$$$ (because we are in case (1)), and similarly $$$f_3(x) = 0$$$ implies $$$f_1(x) = f_3(x)$$$. In both these cases, $$$f_1(x) \geq f_2(x) + f_3(x)$$$.  We can therefore assume that $$$f_2(x), \, f_3(x) > 0$$$.  Since the second and third names are not friends, we have $$$f_1(x) > f_2(x) - 1 + f_3(x) - 1$$$, i.e., $$$f_1(x) \geq f_2(x) + f_3(x) - 1$$$.  Since we are not in case (a), we necessarily have $$$f_1(x) \geq f_2(x) + f_3(x)$$$.