Start learning free

LESSON 172 OF 347 · STRINGS

Palindrome Check in C#: Compare a String with Its Reverse

Practice O(n) Read the full explanation

Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward

Example 1:

Input:  "madam racecar madam"

Output: true

Example 2:

Input:  "abcbx"

Output: false

Note:

Your algorithm should run in O(n) time and use O(1) extra space.


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • s[0] == s[n - 1]
  • s[1] == s[n - 2]
  • s[2] == s[n - 3]
  • ...
How can we check all these pairs of corresponding characters while traversing the string one time?

We can use two pointers! One index variable i starting from the beginning (i = 0) and one index variable j starting from the end of the string (j = n - 1). How should we move these pointers throught the algorithm?

For as long as i < j:
  • 1. We should check if s[i] != s[j] and if so, we conclude the string is not a palindrome and return false.
  • 2. Move i one step to the right.
  • 3. Move j one step to the left.
  • 4. Go to step 1.
If i became greater than or equal to j and we haven't returned false, then we can conclude the string is a palindrome and return true.

STEP 1 OF 2
    Ctrl + Enter to check

    C# · STRINGS

    Palindrome Check in C#, explained

    Problem overview

    The method IsPalindrome takes a string, input, and returns a bool: true if the string reads the same forwards and backwards, false otherwise. Spaces count as characters, so "madam racecar madam" is a palindrome (the answer is true), while "abcbx" is not (the answer is false).

    Approach: reverse, then compare

    The definition of a palindrome gives the algorithm directly. If a string is equal to its own reverse, it is a palindrome. So build the reversed string, then compare it with the original.

    Building the reversal takes one pass over the characters, and the comparison takes one more, so the whole method is linear in the length of the string. The cost is memory: the reversed copy holds as many characters as the input, so this version uses O(n) extra space. The two-pointer idea from the hints, which compares input[i] with input[j] while moving the indexes toward each other, needs only O(1) extra space. This lesson takes the shorter route of a reversed copy first, and the two-pointer version is a natural follow-up.

    Step by step

    1. Build the reversed string. Strings have no Reverse method of their own. LINQ provides one for any sequence, and a string is a sequence of char values, so input.Reverse() yields the characters from last to first. ToArray() collects them into a char[], and new string(...) turns that array into a string.
    2. Compare and return. input == reversedInput is already a bool, so it can be returned directly without an if.

    The solution in C#

    class Solution {
    public bool IsPalindrome(string input) {
        string reversedInput = new string(input.Reverse().ToArray());
        return input == reversedInput;
    }
}

    The C# details behind these two lines:

    • LINQ's Reverse. It is an extension method from the System.Linq namespace, so a file needs using System.Linq; to call it. It doesn't modify the string; it produces a sequence of characters in reverse order, evaluated as ToArray() walks through it.
    • Why new string(...). ToArray() returns a char[], not a string, and the string constructor accepts a char[]. Calling ToString() on the array would give you the type name instead of the text.
    • == compares contents. For two strings, == checks whether they contain the same characters in the same order, not whether they are the same object in memory. The comparison is case-sensitive.
    • Returning a comparison. Writing if (input == reversedInput) return true; else return false; works but is longer; the expression itself is the answer.

    Complexity

    Time: O(n). Producing the reversed characters, collecting them into an array, creating the string and comparing the two strings each take one pass over n characters. A constant number of linear passes is still linear.

    Space: O(n). The array and the new string each hold n characters. An O(1)-space version needs the two-pointer comparison, which checks the string against itself without making a copy.

    Edge cases and common mistakes

    • Empty string. It equals its own reverse, so the result is true.
    • One character. Always a palindrome.
    • Case. "Aba" returns false because 'A' and 'a' are different characters. If a problem wanted case to be ignored, you would lower-case both sides first.
    • Spaces and punctuation. They are compared like any other character, so "A man" is not a palindrome.
    • Missing using System.Linq;. Without it the call to Reverse() on a string doesn't compile.
    • Comparing with ReferenceEquals. That asks whether two variables point to the same object, and a freshly built reversed string never does, so it would return false even for "madam".

    Testing

    • "madam racecar madam" gives true.
    • "abcbx" gives false.
    • "ab" gives false.
    • "a" gives true.
    • "" gives true.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free