King test to his sons
The King of France has turned old. He would like one of his three sons to take up his place
as the next King. But he doesn’t want them to fight over the throne after his death. Over so
many years in the past, his sons have been fighting with each other over trifles. But he feels
that deep inside their hearts, the three brothers love each other. The King believes that he can
bring back the love and harmony among his sons which was present in their childhood. He has
asked Leonardo to help him accomplish this task so that his sons cherish their relationship
again. So, Leonardo has come up with a game that will force all three of them to play together.
The factory, just on the boundary of the kingdom, produces special kind of gold chips. Each
gold chip is inscribed with a lowercase letter of the English alphabet, called its nameLetter.
There is also a unique integer called aurumNumber associated with each gold chip which is
inscribed on the other side of the gold chip. These chips also have special grooves on their ends
which can be used to attach gold chips one after the other and make a long solid linear chain
out of them.
On Leonardo’s advice the King has decided to call all his 3 sons for a small collective exer
cise. Leonardo has made three chains A, B and C containing the same number of gold chips.
The gold chips in each of these chains are arranged in the increasing order of their aurumNum
bers. Leonardo gives a chain to each of the sons. The task given to the sons is that each of
them has to create a chain, for which he may remove some of the gold chips from his chain. It
is necessary that all the three new chains thus created must have the same nameLetters when
read from left to right. All the removed gold chips will be donated for charity. Each new gold
chain must also have the gold chips arranged in the increasing order of their aurumNumber. If
the sons succeed in doing this, they get to keep the gold chain with themselves. They must
donate the entire chain with all of the gold chips for charity if they fail to create such chains.
All of the three sons are very greedy and therefore they want to remove the minimum number
of gold chips from their respective gold chains. You have to find out that what is the minimum
number of total gold chips that the three sons have to donate in order to complete this exercise
The first line of the input contains an integer T which is the number of test cases to follow.
Starting from the next line, each test case consists of three strings A, B and C in separate lines.
Each of these strings is the sequence of nameLetters in the order of the gold chips (which are
arranged in the increasing order of their aurumNumber) in the gold chain.
For each of the test cases, print the minimum number of total gold chips which the three sons
will have to donate for charity.
- 1 ≤ T ≤ 13
- 1 ≤ |A|, |B|, |C| ≤ 450
- |A| = |B| = |C|
- Here, |A| denotes the length of a string A. Similarly |B| for B and |C| for C.
Input: 2 acmicpc acmicpd acdicpc aab aba abb Output: 6 3
Case 1: The gold chips donated by the first son are ‘m’ and ‘c’. The second son donates ‘m’ and ‘d’ and the third son donates ‘d’ and ‘c’. This leaves “acicp” as the nameLetters on the gold chains they create
Case 2: The gold chips donated by the sons are ‘a’, ‘a’ and ‘b’, respectively. This leaves each of them with “ab”.
|Time Limit:||120 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions