Palindrome With Errors - Part 2

Hello folks,

back from a trip to Europe, and with a nasty flu virus type A. In any case, I realized that I never posted the follow-up to the "palindrome with errors" problem - so here it is.
As I had mentioned, a naïve brute-force solution would lead to a runtime of O(2^(length of string)), which given the constraints of length of string <= 120,000, such solution would be intractable.
A slightly better solution is still exponential, but exponential in the max number of errors which the problem limits to 13. The solution below will work in O(3^13), or ~2,000,000 steps, which is super fast.
The idea is to analyze the string as if it was already a palindrome. Therefore, take a look at the extremes of the string. If they match, then it is so far a palindrome. In which case you continue the analysis by moving inwards.
The moment that you determine that the extremes don't match, that's when the exponential aspect will take place. What you'd have to do then is recursively try the following:

• Assume that you remove the leftmost character, and try again
• Assume that you remove the rightmost character, and try again
• Assume that you remove both the leftmost and the rightmost characters, and try again

As you "try again" you increment (accordingly) the number of errors so far. Either the number of errors will be greater than the max allowed, in which case there is no solution, or you'll finally end up with a palindrome, in which case you return. Also, keep track of which indexes you had to remove - you can do so by keeping a hash set. The three calls above are the ones responsible for the "3" in O(3^(max number of errors)).
Notice that the bad side effect of this solution is that if the max number of errors allowed is a huge number, it will be intractable. But given the constraints in the original problem, it should work. As an example, here is a run when the max number of errors allowed was set to 15:

 Code is down below, thanks, Marcelo.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PalindromeWithErrorsEx
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length != 2)
            {
                Console.WriteLine("Usage: PalindromeWithErrorsEx.exe <max number of errors> <random string length>");
                return;
            }

            int maxNumberOfErrorsAllowed = Convert.ToInt32(args[0]);
            int stringLen = Convert.ToInt32(args[1]);

            string str = GenerateRandomString(stringLen);
            Console.WriteLine("Random Input String: {0}", str);
            Console.WriteLine();
            HashSet<int> indexesToBeRemoved = new HashSet<int>();

            if (RemoveErrorsToGeneratePalindrome(str,
                                                0,
                                                str.Length - 1,
                                                maxNumberOfErrorsAllowed,
                                                0,
                                                indexesToBeRemoved))
            {
                Console.WriteLine("Found Solution!");
                Console.WriteLine();

                Console.WriteLine("Need to remove {0} characters:", indexesToBeRemoved.Count);
                foreach (int i in indexesToBeRemoved)
                {
                    Console.WriteLine("Remove index {0} ({1})", i, str[i]);
                }
                Console.WriteLine();

                string palindromeStr = "";
                for (int i = 0; i < str.Length; i++)
                {
                    if (!indexesToBeRemoved.Contains(i))
                    {
                        palindromeStr += str[i].ToString();
                    }
                }
                Console.WriteLine("Palindrome: {0}", palindromeStr);
            }
            else
            {
                Console.WriteLine("Solution Not Found!");
            }
        }

        static string GenerateRandomString(int len)
        {
            string chars = "abcdefg".ToUpper();
            Random rd = new Random();

            string str = "";
            for (int i = 0; i < len; i++)
            {
                str += chars[rd.Next(0, chars.Length)].ToString();
            }

            return str;
        }

        static bool RemoveErrorsToGeneratePalindrome(string str,
                                                     int beginIndex,
                                                     int endIndex,
                                                     int maxNumberErrorsAllowed,
                                                     int currentNumberErrors,
                                                     HashSet<int> indexesToBeRemoved)
        {
            if (currentNumberErrors > maxNumberErrorsAllowed)
            {
                return false;
            }
            if (beginIndex >= endIndex)
            {
                return true;
            }

            if (str[beginIndex] == str[endIndex])
            {
                return RemoveErrorsToGeneratePalindrome(str,
                                                        beginIndex + 1,
                                                        endIndex - 1,
                                                        maxNumberErrorsAllowed,
                                                        currentNumberErrors,
                                                        indexesToBeRemoved);
            }
            else
            {
                //Attempt to remove the last index
                if (!indexesToBeRemoved.Contains(endIndex))
                {
                    indexesToBeRemoved.Add(endIndex);
                }

                if (RemoveErrorsToGeneratePalindrome(str,
                                                    beginIndex,
                                                    endIndex - 1,
                                                    maxNumberErrorsAllowed,
                                                    currentNumberErrors + 1,
                                                    indexesToBeRemoved))
                {
                    return true;
                }

                if (indexesToBeRemoved.Contains(endIndex))
                {
                    indexesToBeRemoved.Remove(endIndex);
                }

                //Attempt to remove the first index
                if (!indexesToBeRemoved.Contains(beginIndex))
                {
                    indexesToBeRemoved.Add(beginIndex);
                }

                if (RemoveErrorsToGeneratePalindrome(str,
                                                    beginIndex + 1,
                                                    endIndex,
                                                    maxNumberErrorsAllowed,
                                                    currentNumberErrors + 1,
                                                    indexesToBeRemoved))
                {
                    return true;
                }

                if (indexesToBeRemoved.Contains(beginIndex))
                {
                    indexesToBeRemoved.Remove(beginIndex);
                }

                //Attempt to remove both the first and the last indexes
                if (!indexesToBeRemoved.Contains(beginIndex))
                {
                    indexesToBeRemoved.Add(beginIndex);
                }
                if (!indexesToBeRemoved.Contains(endIndex))
                {
                    indexesToBeRemoved.Add(endIndex);
                }

                if (RemoveErrorsToGeneratePalindrome(str,
                                                    beginIndex + 1,
                                                    endIndex - 1,
                                                    maxNumberErrorsAllowed,
                                                    currentNumberErrors + 2,
                                                    indexesToBeRemoved))
                {
                    return true;
                }

                if (indexesToBeRemoved.Contains(endIndex))
                {
                    indexesToBeRemoved.Remove(endIndex);
                }
                if (indexesToBeRemoved.Contains(beginIndex))
                {
                    indexesToBeRemoved.Remove(beginIndex);
                }
            }

            return false;
        }
    }
}