Get all possible palindromes in C#

Question

As the title says, the goal is to get all the possible palindromes of a string in C#:

public static bool IsPalindrome(this string source)
{
 for(int i = 0; i < source.Length / 2; i++)
 {
 if(source[i] != source[source.Length - 1 - i])
 {
 return false;
 }
 }
 return true;
}
public static IEnumerable<string> GetPossiblePalindromes(this string source, int maxPossibleChanges, IEnumerable<char> alphabet)
{
 var executionStack = new Stack<Tuple<string, int>>();
 executionStack.Push(Tuple.Create(source, 0));
 int maxChanges = Math.Min(maxPossibleChanges, source.Length);
 var generated = new HashSet<string>();
 generated.Add(source);
 if(maxPossibleChanges < 0)
 {
 yield break;
 }
 do
 {
 Tuple<string, int> currentRecord = executionStack.Pop();
 string currentString = currentRecord.Item1;
 if (currentString.IsPalindrome())
 {
 yield return currentString;
 }
 int currentNumberOfChanges = currentRecord.Item2;
 if (currentNumberOfChanges == maxChanges)
 {
 continue;
 }
 char[] chars = currentString.ToArray();
 foreach(char character in alphabet)
 {
 for(int i = 0; i < currentString.Length; i++)
 {
 char old = chars[i];
 if(character == old)
 {
 continue;
 }
 chars[i] = character;
 var newString = new string(chars);
 if (generated.Contains(newString))
 {
 chars[i] = old;
 continue;
 }
 generated.Add(newString);
 executionStack.Push(Tuple.Create(newString, currentNumberOfChanges + 1));
 chars[i] = old;
 }
 }
 } while (executionStack.Count > 0);
 yield break;
}

Case sensitivity is taken into account and there is a max number of changes one can make to the original string in order to make it a palindrome. Also, a 1 charactes string is not considered a palindrome.

I wanted to ask for a review. I'm more interested in performance reviews but all the other reviews are more than welcome.

• Denis: Please include all methods written by you e.g IsPalindrome they also affect the performance of your program.
• Denis: Also you need to provide more information on what specific palindromes do you consider. Is case sensitivity a thing ? Does a single character counts as a palindrome ?
• Gentian Kasa: @denis, I added some more info. Thanks for pointing that out.

Answer 1

First and foremost your code is solving a different problem from the one stated in the question Get all the possible palindromes of a string or at least that's what it looks like and as pointed in my comments you need to provide more details and context about the code.

I will try to make a few points concerning your existing code aside from it being overly-complicated :

1. Do you really need an iterator here ? What's the point of saving the state of this code ? You clearly want all the possible palindromes from a specified string which to me sounds like I would receive a List<string> containing all the palindromes in there.

2. Usually converting string to char array is redundant but if you really need to do that you are better off using string.ToCharArray() instead of string.ToArray() detailed explanation why is given here.

3. Contains() is O(n) operation so you should avoid it if possible

4. It might be a good idea to replace that Tuple<string, int> with a class, but I'm not sure what is the point of having it in the first place.

I will provide an alternative solution to the problem :

Get all the possible palindromes of a string with length more than 1.

First let's start by declaring a method that decides if a string is a palindrome.

private static bool IsPalindrome(string input)
{
 for (int i = 0; i < input.Length; i++)
 {
 if (input[i] != input[input.Length - 1 - i])
 {
 return false;
 }
 }
 return true;
}

Here we are making use of the fact that string is already a char[] and we can simply avoid the redundant call ToCharArray(). Also we are using only a single for loop and we are returning as soon as we find 2 different characters to increase performance.

This can also be converted to a one-liner using LINQ

private static bool IsPalindrome(string input)
{
 return !input.Where((t, i) => t != input[input.Length - 1 - i]).Any();
}

or with C# 6

private static bool IsPalindrome(string input) => !input.Where((t, i) => t != input[input.Length - 1 - i]).Any();

Next we need to actually make use of that method and get all of the possible palindromes of a string :

private static List<string> GetPalindromes(string source)
{
 List<string> subsets = new List<string>();
 for (int i = 0; i < source.Length - 1; i++)
 {
 for (int j = i + 1; j <= source.Length; j++)
 {
 if (j - i > 1 && source[j - 1] == source[i])
 {
 string currentSubset = source.Substring(i, j - i);
 if (IsPalindrome(currentSubset))
 {
 subsets.Add(currentSubset);
 }
 }
 }
 }
 return subsets;
}

This chunk of code is what I would like to have as I explained in my first point but if you really need an iterator :

public static IEnumerable<string> GetPalindromes(this string source)
{
 for (int i = 0; i < source.Length - 1; i++)
 {
 for (int j = i + 1; j <= source.Length; j++)
 {
 if (j - i > 1 && source[j - 1] == source[i])
 {
 string currentSubset = source.Substring(i, j - i);
 if (IsPalindrome(currentSubset))
 {
 yield return currentSubset;
 }
 }
 }
 }
}

• Dmitry: In your first IsPalindrome implementation it's enough to iterate up to input.Length / 2. So the next 2 LINQ one-liners are two times less efficient in the case if the input is palindrome.