Smallest Hamming distance to a palindrome containing a substring

Pyth, 19 bytes

hSmsnVQd/#z_I#^+Qzl

Demonstration

Extreme brute force approach. Generate all strings of the appropriate length with characters in either string, filter for palindromes and for containing the second input, map to hamming distance from first string, output smallest.

Explanation:

hSmsnVQd/#z_I#^+Qzl
hSmsnVQd/#z_I#^+QzlQ     Variable introduction
                         Q = string A, z = string B.
               +Qz       Concatenate A and B
              ^   lQ     Form every string of length equal to len(A)using
                         characters from the concatenation.
             #           Filter on
           _I            Invariance under reversal (palindrome)
         #               Filter on
        / z              Nonzero occurences of B
  m                      Map to
    nV                   !=, vectorized over
      Qd                 A and the map input
   s                     Sum (gives the hamming weight)
hS                       Min

Pyth, 45 bytes

hSmsnVQdf}zTsmm+hc2KsXcd+Bklz1z_hc2PKh-lQlz_B

Try it online. Test suite.

I'm still not exactly satisfied with how this turned out. But at least it's quite hard to understand without an explanation now. (Success, I guess?)

Explanation

• Take in A as Q and B as z.
• m…_BQ Compute the following for both A and its reverse as d:
  • m…h-ldlz Compute the following for all k from 0 to len(A) - len(B) inclusive:
    • +Bklz Get the pair k, k + len(B).
    • cd Split d at those indices.
    • X…1z Replace the second (middle) part with B.
    • Ks Concatenate the pieces and save to K. B is now inserted at position k in A or its reverse.
    • hc2 Split the resulting string in two and keep the first piece. This gives half of the string with the possible middle character.
    • hc2PK Remove the last character and do the same split, keeping the first piece. This gives half of the string without the possible middle character.
    • +…_ Add the reverse of the shorter piece to the longer piece. We now have a palindrome.
• s Concatenate the results for A and its reverse.
• f}zT Remove all strings that don't contain B.
• m Compute the following for all the resulting strings d:
  • nVQd Get the pairwise inequality with A. This gives True for pairs that need to be changed.
  • s Sum the list. This gives the Hamming distance.
• hS Take the minimum result.