Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. String

Valid Palindrome

String, Two Pointers

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

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

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

  1. The input string s consists only of printable ASCII characters.

  2. The string s can be empty.

  3. The string s can contain spaces, punctuation, and other non-alphanumeric characters.

  4. The string s can contain both uppercase and lowercase letters.

Questions to Clarify:

  1. Case Sensitivity: Should the palindrome check be case-sensitive or case-insensitive? The problem statement suggests it should be case-insensitive, but it would be good to confirm this.

  2. Non-Alphanumeric Characters: Should non-alphanumeric characters be ignored when checking for a palindrome? The problem statement suggests they should be, but again, it would be good to confirm this.

  3. Null Input: How should the function handle a null input? Should it return true (since a null string can be considered a special case of an empty string), false, or should it throw an exception?

  4. Large Inputs: What is the maximum length of the input string s? This could affect the choice of algorithm, especially for very long strings.

  5. Performance Requirements: Are there any performance requirements or constraints? For example, does the function need to run in a certain amount of time or use a certain amount of memory?

Solutions

Please note that this function considers an empty string and a null string as palindromes, which is consistent with the definition of a palindrome. An empty string reads the same forward and backward, and a null string can be considered a special case of an empty string. However, some people might argue that a null string should not be considered a palindrome, so you might want to handle this case differently depending on your specific requirements.

Approach – Brute Force Technique

The code first converts the string to lowercase and filters out non-alphanumeric characters. It then checks each character from the start of the string to the middle against the corresponding character from the end. If it finds a pair of characters that don’t match, it immediately returns false. If it doesn’t find any mismatched pairs, it returns true after checking all pairs.

Steps

  1. Check if the string is not null: The if (s is not null) statement checks if the input string s is not null. If s is null, the function will skip the rest of the code and return true.

  2. Convert to lowercase and filter out non-alphanumeric characters: The Span<char> str = s.ToLower().Where(c => char.IsLetterOrDigit(c)).ToArray(); statement does three things:

    • s.ToLower() converts all characters in the string s to lowercase.

    • Where(c => char.IsLetterOrDigit(c)) filters out any characters that are not letters or digits.

    • ToArray() converts the result back into an array of characters.

  3. Check each character pair: The for (int i = 0; i < len / 2; i++) loop iterates over each character in the first half of the string str. For each character, it checks if it is the same as the corresponding character from the end of the string. If the characters are not the same, the function immediately returns false.

  4. Return true if no mismatches are found: If the function has checked all character pairs and hasn't found any mismatches, it returns true.

public class Solution
{
    public bool IsPalindrome(string s)
    {
        if (s is not null)
        {
            // N times
            Span<char> str = s.ToLower().Where(c => char.IsLetterOrDigit(c)).ToArray();
            var len = str.Length;
            for (int i = 0; i < len / 2; i++) //log N times
            {
                if (str[i] != str[len - i - 1])
                    return false;
            }
        }
        return true;
    }
}

Complexity

  • Time complexity: O(N)

  • Space complexity: O(N)

Approach – Two Pointers Technique

Two pointers to compare characters without creating a new string.

Steps

  1. Initialize two pointers: The int i = 0, j = s.Length - 1; line initializes two pointers, i and j. i starts at the beginning of the string s and j starts at the end.

  2. Start of the loop: The while (i < j) line starts a loop that continues as long as i is less than j. This means the loop will continue until the two pointers meet or cross each other.

  3. Skip non-alphanumeric characters from the start: The while (i < j && !Char.IsLetterOrDigit(s[i])) i++; line inside the loop skips any non-alphanumeric characters from the start of the string. It does this by checking if the character at the ith position is a letter or digit, and if it's not, it increments i to move to the next character.

  4. Skip non-alphanumeric characters from the end: The while (i < j && !Char.IsLetterOrDigit(s[j])) j--; line inside the loop skips any non-alphanumeric characters from the end of the string. It does this by checking if the character at the jth position is a letter or digit, and if it's not, it decrements j to move to the previous character.

  5. Compare characters: The if (Char.ToLower(s[i]) != Char.ToLower(s[j])) return false; line inside the loop compares the characters at the ith and jth positions. If they are not the same, it returns false, indicating the string is not a palindrome.

  6. Move the pointers: The i++; j--; lines inside the loop move the pointers towards each other. This prepares for the next iteration of the loop, where the next pair of characters will be compared.

  7. Return true: The return true; line after the loop returns true, indicating the string is a palindrome. This line is only reached if all pairs of characters have been compared and no mismatches have been found.

public class Solution
{
    public bool IsPalindrome(string s)
    {
        int i = 0, j = s.Length - 1;
        while (i < j)
        {
            while (i < j && !Char.IsLetterOrDigit(s[i])) i++;
            while (i < j && !Char.IsLetterOrDigit(s[j])) j--;
            if (Char.ToLower(s[i]) != Char.ToLower(s[j]))
            {
                return false;
            } 
            i++;
            j--;
        }
        return true;
    }
}

Complexity

  • Time complexity: O(N)

  • Space complexity: O(1)

PreviousLongest Substring Without Repeating CharactersNextValid Palindrome II

Last updated 1 year ago