#codingexercise
For a given string and an integer k, find if the string can form a palindrome by removing k characters

Bool IsKPalindrome(string s, int k) 

{ 

If (String.IsNullOrEmpty(s) || k < 0 || k > s.Length) return false; 

Void combinations = new List<string>(); 

Var b = new StringBuilder(s.Length); 
for (int i =0; i< s.Length; i++)
b.Append("\0");

Int start = 0; 

Int level = 0; 

Int length = s.Length - k; 

Combine(s, start, level, length, ref b, ref combinations); 

Return combinations.Any(x=>IsPalindrome(x)); 

}

There's also a variation of the problem where we can look for at most k character removal

This is done by comparing the string to its reverse to see if the edit distance based on deletions alone can cost less than or equal to k

int GetKPalin(string str, string rev, int m, int n)

{

if (m == 0) return n;

if (n == 0) return m;

if (str[m-1] == rev[n-1])

   return GetKPalin(str, rev, m-1, n-1);

return 1 + Math.min(GetKPalin(str, rev, m-1, n), GetKPalin(str, rev, m, n-1));

}

bool isKPalin(string str, int k)

{

string rev = str.reverse();

return GetKPalin(str, rev, str.Length, rev.Length) <= k * 2);

}

The costing can also be based on longest common subsequence.

Note that we can also make early exclusions with a frequency table.

For example:

var h = new Hashtable();

for (int i = 0; i < str.Length; i++)

if (h.Contains(str[i])) h[str[i]]++;

else h.Add(str[i], 1);
int pairs = h.Keys.Count(x => h[x]%2 == 0);
int odd = h.Keys.Count(x=>h[x]%2 == 1);
int singles = h.Keys.Count(x=>h[x] == 1);
// we can check conditions for false and return earlier
If order were not important, we can also check for qualifying strings
// if (pairs.Count > 0 && singles.Count <=k &&  odd.Count <=1 ) return true;