Conversion to palindrome with minimal points used

Spent about an hour and got a working solution that I believe should give an optimal result:

public class PalindromeFinder : IComparer<Tuple<int,string>> { public PalindromeFinder() { heap = new IntervalHeap<Tuple<int, string>>(this); handles = new Dictionary<string, IPriorityQueueHandle<Tuple<int, string>>>(); } private readonly IntervalHeap<Tuple<int, string>> heap; private readonly Dictionary<string, IPriorityQueueHandle<Tuple<int, string>>> handles; public int FindMinValue(string startingWord) { AddWord(startingWord,0); while(!heap.IsEmpty) { var item = heap.DeleteMin(); var word = item.Item2; var value = item.Item1; handles.Remove(word); if(IsPalindrome(word)) { return value; } for(int i = 0; i<word.Length; i++) { //decrease var decreased = word.ToCharArray(); if (decreased[i] > 'a') { decreased[i]--; AddWord(new string(decreased), value + 4); } //switch for(int j = i+1; j<word.Length; j++) { if (word.Count(x => x == word[i]) >= 2 || word.Count(x => x == word[j]) >= 2) { var swap = word.ToCharArray(); var tmp = swap[i]; swap[i] = swap[j]; swap[j] = tmp; AddWord(new string(swap), value + 7); } } //add character before (only add characters already present) foreach (char c in word.Distinct()) { var added = word.Insert(i, c.ToString()); AddWord(added, value+12); } } //add character at end of word foreach (char c in word.Distinct()) { var added = word + c.ToString(); AddWord(added, value + 12); } } return int.MaxValue; } private void AddWord(string word, int value) { var min = int.MaxValue; if(handles.ContainsKey(word)) { var tuple = heap.Delete(handles[word]); min = tuple.Item1; handles.Remove(word); } IPriorityQueueHandle<Tuple<int, string>> handle = null; heap.Add(ref handle,new Tuple<int, string>(Math.Min(min, value), word)); handles[word] = handle; } private bool IsPalindrome(string word) { int left = 0; int right = word.Length - 1; while(left<right) { if (word[left] != word[right]) return false; left++; right--; } return true; } public int Compare(Tuple<int, string> x, Tuple<int, string> y) { return x.Item1 - y.Item1; } } 

Uses priority queue implementation from C5 collections. This is basically the brute force best-first search solution to the problem. It runs out of memory pretty fast, and is less efficient than is probably possible. I could fix that by implementing a better data structure like a DAWG, but out of time for now. Maybe later.It does work well for short words, and even for long ones that are within a few steps of a palindrome already.

Edit:

Made some improvements on Peter's suggestion, but the complexity is still too high. On input: "superman", runs for about a minute until it runs out of memory with over 11 million items in heap and a max value of 42 reached. Still a bit off from being a viable general solution.