I am a C# developer and I am training my coding and algorithm skills on LeetCode.
And now I am handling the problem 5: longest palindromic substring.
I want someone can explain the reason.
My solution version 1 to this problem was:

public string LongestPalindrome(string s)
{
    // Step 0: Handles invalid or special cases.
    if (string.IsNullOrWhiteSpace(s) ||
        s.Length == 1 ||
        s.Distinct().Count() == 1 ||
        s.Reverse().SequenceEqual(s))
        {
            return s;
        }

        if (s.Length == 2)
        {
            return s.First().Equals(s.Last()) ? s : s.First().ToString();
        }

        if (s.Distinct().Count() == s.Length)
        {
            return s.First().ToString();
        }

        // Step 1: Handles normal cases.
        var longestPalindromeSubstring = string.Empty;

        for (var index = 0; index < s.Length && s.Length - index > longestPalindromeSubstring.Length; index  )
        {
            var currentChar = s[index];
            var currentCharLastIndex = s.LastIndexOf(currentChar);

            if (index == currentCharLastIndex)
            {
                if (!string.IsNullOrWhiteSpace(longestPalindromeSubstring) ||
                        longestPalindromeSubstring.Length > 1)
                {
                    continue;
                }

                longestPalindromeSubstring = currentChar.ToString();
            }

            var currentCharIndexes = new Stack<int>();

            for (var nextIndex = index   1; nextIndex <= currentCharLastIndex; nextIndex  )
            {
                if (s[nextIndex] == currentChar)
                {
                    currentCharIndexes.Push(nextIndex);
                }
            }

            while (currentCharIndexes.Any())
            {
                var relatedIndex = currentCharIndexes.Pop();
                var possibleStr = s.Substring(index, relatedIndex - index   1);
                var reversedPossibleStr = new string(possibleStr.Reverse().ToArray());

                if (!possibleStr.Equals(reversedPossibleStr) ||
                    possibleStr.Length < longestPalindromeSubstring.Length ||
                    possibleStr.Equals(longestPalindromeSubstring))
                {
                    continue;
                }

                longestPalindromeSubstring = possibleStr;
            }
        }

        return longestPalindromeSubstring;
    }

However this solution above was failed to pass the LeetCode validation since the issue: Time Limit Exceeded.
Then I just made a small update, and the solution version 2 passed, the changed part was only adding ToCharArray() method before invoking Reverse() method:

var reversedPossibleStr = new string(possibleStr.ToCharArray().Reverse().ToArray());

if (!possibleStr.Equals(reversedPossibleStr) ||
     possibleStr.Length < longestPalindromeSubstring.Length ||
     possibleStr.Equals(longestPalindromeSubstring))
{
     continue;
}
…………

But I am not sure the reason why it can work, I just guessed that the data in an array will be arranged in a sequence memory space, it may help to improve the performance, could someone explain more detail. Thank you in advance.

CodePudding user response：

The Reverse method uses EnumerableHelpers.ToArray to fetch the count of the input enumerable. If the enumerable doesn't implement ICollection<T> interface, it will use a list-like approach to creates an array which will extend the array many times. Unfortunately string doesn't implement ICollection<char>, though it knows how many characters it contains, so string.Reverse() is slower than string.ToCharArray().Reverse().