Creating a super-efficient Valid Palindrome algorithm in C#

#algorithms #beginners #tutorial #csharp

First, do you know what a Palindrome is? No? So, according to the first Google result: A palindrome is a word, phrase, number, or sequence that reads the same backward as forward. The term originates from the Greek word "palindromos", meaning "running back again".

Secondly, are you able to verify whether a string is a valid palindrome in an algorithm created with C#? This is the problem we're going to solve today🫡.

The problem: Given a string s, return true if it is a palindrome, or false otherwise.

Example: Input: s = "Step on no pets" | Output: true
Explanation: "steponnopets" is a palindrome.

💡 Analyzing the problem

To determine if a string is a palindrome, the main idea is to check if it reads the same forward and backward.

However, real-world examples like "Step on no pets" usually have a catch: case sensitivity (capital 'S' vs lowercase 's') and non-alphanumeric characters: spaces, punctuation, or symbols, etc... To solve this effectively, we can follow a two-step process:

Clean the string
Check for symmetry

The Step-by-Step Strategy

Step 1: Clean the Input

Before doing any comparisons, we need to normalize the string so that formatting doesn't get in the way.

Convert everything to lowercase so 'S' and 's' match.
Remove all non-alphanumeric characters (spaces, commas, periods, etc.). For your example, Original: "Step on no pets" --> Cleaned: "steponnopets"

Step 2: The Two-Pointer Approach

The most efficient way to check for a palindrome is to use two pointers (or indices): one starting at the very beginning (left) of the cleaned string, and one at the very end (right).

Compare the character at the left pointer with the character at the right pointer.
If they match, move the left pointer one step right, and the right pointer one step left.
If they don't match, you can stop immediately and return false, definitively it's not a palindrome.
Repeat this until the pointers meet or cross in the middle. If you make it to the middle without any mismatches, return true.

🛠️Hands on

In C# we can do the following:

public class Solution {
    public bool IsPalindrome(string s) {
        int left = 0;
        int right = s.Length - 1;

        while (left < right) {
            if (!char.IsLetterOrDigit(s[left])) {
                left++;
            }
            else if (!char.IsLetterOrDigit(s[right])) {
                right--;
            }
            else {
                if (char.ToLowerInvariant(s[left]) != char.ToLowerInvariant(s[right])) {
                    return false; 
                }
                left++;
                right--;
            }
        }

        return true;
    }
}

The solution: The Two-Pointer Approach

Instead of creating a brand new "cleaned" string (which takes up extra memory), this solution moves the pointers across the original string and simply skips over any spaces or punctuation on the fly. This optimizes our space complexity to O(1).

First, we Initialize pointers at the beginning and end of the string. Then, while left is lass than right:
Verify if left index is letter or digit, if it's affirmative, move the left pointer right (left++).
Verify if right index is letter or digit, if it's affirmative, move the right pointer left (right++).
If both are alphanumeric, compare them case-insensitively. If the left index is different from the right index, so, an incompatibility was found. It returns false.
Left is incremented and right decremented.
Finally, if all valid pairs matched, return true (valid palindrome)

1. ⏳ Time Complexity: O(n)

What it means: The time it takes to run the code grows linearly with the length of the string (n).

Why: In the worst-case scenario (when the string is a palindrome), the left and right pointers start at the edges and meet exactly in the middle. This means every character in the string is inspected exactly once.

Even though we skip non-alphanumeric characters, each character is still visited only a single time by one of the pointers.

2. 📦 Space Complexity: O(1)

What it means: The memory used by the algorithm is constant, meaning it stays the same no matter how massive the input string gets.

Why: Unlike the LINQ approach (or solutions in other languages that create a brand-new, filtered version of the string), this method processes the original string in place.

The only extra memory allocated during execution is for a couple of primitive integer variables (left and right) to track the array indices.