I think your question could be stated as:
- Determine the minimum number of letters to be added to a given string in order to make it into a palindrome.
You can do some work analytically. I'll use upper-case letters A, B, C, ... for the given letters; I'll use lower-case letters a, b, c for those added to make a palindrome.
- For an L-character string, the maximum number of characters that must be added is L-1.
- In general, there are numerous ways to make a palindrome from a string.
- Any single character is already a palindrome (L-1 = 0).
- For a two-character string, there are two cases:
- AA (0 to add; it is already a palindrome).
- AB (1 to add — bAB or ABa).
- For a three-character string, there are
four five cases:
- ABC (2 to add — cbABC).
- AAB (1 to add — bAAB).
- ABB (1 to add — ABBa).
- ABA (0 to add; it is already a palindrome).
- AAA (0 to add; it is already a palindrome).
- For a four-character string, there are at least ten cases:
- ABCD (3 to add — dcbABCD).
- AABC (2 to add — cbAABC).
- ABAC (1 to add — cABAC).
- ABCA (1 to add — ABCbA).
- ABBA (0 to add; it is already a palindrome).
- ABAA (1 to add — ABAbA).
- ABAB (1 to add — bABAB).
- ABBB (1 to add — ABBBa).
- AAAA (0 to add; it is already a palindrome).
- AABB (2 to add — bbAABB).
Starting with these cases, we can see that:
- Check whether the pattern is a palindrome.
- If yes, the number of characters to add is 0.
- Given the length, L, and the number of distinct characters, D,
- If L = D, then you need to add L-1 characters.
- Otherwise, you can lop off the last character, make an palindrome from the L-1 character string, and add the last character again at front and back.
- That's a nice recursive function.
- The question is, does that add the minimum characters each time?
Let's revisit the case of L=4. X will be the number of extra characters required.
- ABCD
- Drop D, palindrome from ABC (L=3, D=3)
- Drop C, palindrome from AB (L=2, D=2)
- Drop B, palindrome from A (L=1, D=1)
- A is a palindrome ⟶ A (X=0)
- Add B to front and back ⟶ bAB (X=1)
- Add C to front and back ⟶ cbABC (X=2)
- Add D to front and back ⟶ dcbABCD (X=3)
- AABC
- Drop C, palindrome from AAB (L=3, D=2)
- Drop B, palindrome from AA (L=2, D=1)
- AA is a palindrome ⟶ AA (X=0)
- Add B to front and back ⟶ bAAB (X=1)
- Add C to front and back ⟶ cbAABC (X=2)
- ABAC
- Drop C, palindrome from ABA (L=3, D=2)
- ABA is a palindrome ⟶ ABA (X=0)
- Add C to front and back ⟶ cABAC (X=1)
- ABBA
- ABBA is a palindrome ⟶ ABBA (X=0)
- ABAA
- Drop A, palindrome from ABA (L=3, D=2)
- ABA is a palindrome ⟶ ABA (X=0)
- Add A to front and back ⟶ aABAA (X=1)
- ABAB
- Drop B, palindrome from ABA (L=3, D=2)
- ABA is a palindrome ⟶ ABA (X=0)
- Add B to front and back ⟶ BABAB (X=1)
- AAAA
- ABBA is a palindrome ⟶ ABBA (X=0)
- AABB
- Drop B, find palindrome from AAB (L=3, D=2)
- Drop B, find palindrome from AA (L=2, D=1)
- AA is a palindrome ⟶ AA (X=0)
- Add B to front and back ⟶ bAAB (X=1)
- Add B to front and back ⟶ bbAABB (X=2)
So far, so good...but there are two cases not treated:
- ABBB
- In this example, dropping the last character is bad; it leads to bbbABBB, which is much longer than what you get if you drop the first character (namely ABBBa).
- ABCA
- In this example, if you go about dropping the last character, you also end up with a much longer string than is necessary.
How can we refine things?
If the first and last character are the same (but the string is not a palindrome), then drop first and last character, find a palindrome for the shorter string, and then reinstate the first and last. For the ABCA example, that gives:
- ABCA
- Drop leading and trailing A; palindrome from BC (L=2, D=2)
- Drop C; palindrome from B (L=1, D=1)
- B is a palindrome ⟶ B (X=0)
- Add C at front and back ⟶ cBC (X=1)
- Add A at front and back ⟶ AcBCA (X=1 — because we removed 2 and restored 2)
That still leaves the ABBB example causing grief. We can note that AAAB is very similar to ABBB, but AAAB would work fine with the algorithm originally proposed, producing BAAAB (X=1).
Maybe the trick is to find the longest sequence of a single character repeating at either end. If the longer of these is L/2 or greater, then you simply add the other part as a 'mirror' of itself. With the AAAB and ABBB cases:
- The longest repeat is 3 (AAA or BBB); and that's more than L/2, so the other part is added as a mirror of itself (but a mirror of 1 letter is that letter).
- AAAB adds the B in mirror, producing BAAAB (X=1).
- ABBB adds the A in mirror, producing ABBBA (X=1).
- Applied to AABB, there are two different 2-letter sequences, which are both L/2 long; it is arbitrary which is processed, and you end up with either BBAABB or AABBAA (X=2).
Looking at a longer sample, what about AACADEFFFFABA?
- The strings start and end with A; remove it and find a palindrome for ACADEFFFFAB.
- Arbitrarily drop B; find a palindrome for ACADEFFFFA.
- The strings start and end with A; find a palindrome for CADEFFFF.
- There's a run of 4 F's at the end; that's L/2.
- Add the mirror of CADE to give a palindrome ⟶ CADEFFFFEDAC (X=4)
- Add A to both ends ⟶ ACADEFFFFEDACA (X=4)
- Add B to both ends ⟶ BACADEFFFEDACAB (X=5)
- Add A to both ends ⟶ ABACADEFFFFEDACABA (X=5)
That seems to be about right...
Let's look at another longer sample:
- ABCDEFCBA
- Drop the leading and trailing A's; find a palindrome for BCDEFCB.
- Drop the leading and trailing B's; find a palindrome for CDEFC.
- Drop the leading and trailing C's; find a palindrome for DEF.
- Drop the F; find a palindrome for DE.
- Drop the E; find a palindrome for D.
- D is a palindrome ⟶ D (X=0).
- Add E to front and back ⟶ EDE (X=1).
- Add F to front and back ⟶ FEDEF (X=2).
- Add C to front and back ⟶ CFEDEFC (X=2).
- Add B to front and back ⟶ BCFEDEFCB (X=2).
- Add A to front and back ⟶ ABCFEDEFCBA (X=2).
That too looks about right.
From here, I think it is a SMOP (Simple Matter of Programming).
[Later] There is probably still some refinement required...
Consider:
CABLEWASIEREISAWELBA (C Able Was I Ere I Saw Elba)
Clearly, the minimum change is to add a C to the end:
CABLEWASIEREISAWELBAc
When I first wrote up the 'longest repeat' criterion, I had 'longest palindrome', and that was probably a better choice. In this case, the longest palindrome from the end is clearly everything except the leading C, and then you end up with the minimum change. A repeat is a special case of palindrome, of course.
It does lead to the question of what happens with:
XYZABLEWASIEREISAWELBAOBSEQUIOUSNESS
There, you have a 17-letter anagram (Able ...) with 16 letters surrounding it. Does that help at all? A little. As you strip off the end characters (from OBSEQUIOUSNESS), you eventually end up with the anagram exposed, at which point you generate:
XYZABLEWASIEREISAWELBAzyx
and then you add back the OBSEQUIOUSNESS to yield:
ssensuoiuqesboXYZABLEWASIEREISAWELBAzyxOBSEQUIOUSNESS
So, the longest trailing or leading palindrome refinement seems to be about right.
How should the tests be prioritized? Should the leading/trailing palindrome be found before the leading/trailing same letter? Consider:
AABLEWASIEREISAWELBA (A Able Was I Ere I Saw Elba)
The leading and trailing letters are the same, but there's the humongous trailing anagram.
If you drop the leading and trailing A, then you process:
ABLEWASIEREISAWELB
The leading/trailing letters are different, so the trailing palindrome is spotted, and you end up with:
AABLEWASIEREISAWELBaA
If you did the trailing palindrome first, you end up with essentially the same answer:
AABLEWASIEREISAWELBAa
So, maybe the sequencing is not critical. The common letter at the end is simpler than 'the longest leading/trailing palindrome', so that makes sense as the test to perform first, unless someone devises an example where it leads to the wrong answer.