DouKaku?

(defun random-char (&optional random-state)
  (code-char (+ 65 (random 26 random-state))))

(defun random-string (length &optional random-state)
  (let ((s (make-string length)))
    (dotimes (i length)
      (setf (elt s i) (random-char random-state)))
    s))

(defun modify (s &optional random-state)
  (let ((i (random (length s) random-state))
        (r (copy-seq s)))
    (setf (elt r i)
          (code-char (+ (random 3 random-state)
                        (char-code (elt s i))
                        -1)))
    r))

(defun weasel (target)
  (let ((state (make-random-state t)))
    (flet ((key (s)
             (loop for c1 across s and c2 across target
               sum (abs (- (char-code c1) (char-code c2))))))
      (do ((strings (loop repeat 300
                      as s = (random-string (length target) state)
                      collect (cons s (key s)))
                    (sort (mapcan (lambda (p)
                                    (loop repeat 3
                                      as s = (modify (car p) state)
                                      collect (cons s (key s))))
                                  strings)
                          #'< :key #'cdr))
           (i 1 (1+ i)))
          ((string= target (caar strings))
           (format t "~D: ~A (~D)~%" i (caar strings) (cdar strings))
           (format t "Finished after ~D steps.~%" i))
        (setf (cdr (nthcdr 299 strings)) nil)
        (format t "~D: ~A (~D)~%" i (caar strings) (cdar strings))))))

(weasel "METHINKSITISAWEASEL")