101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Two Pointers Approach - Complex approach
  2. Reverse and Compare Approach - Complex approach

Handling Non-Alphanumeric Characters

Before checking if a string is a palindrome, we need to handle non-alphanumeric characters and case sensitivity.

  1. Remove or ignore all non-alphanumeric characters (spaces, punctuation, etc.)
  2. Convert all characters to the same case (lowercase or uppercase)
  3. After these preprocessing steps, we can apply our palindrome checking algorithm

Example:

Original:
A man, a plan, a canal: Panama
Cleaned:
amanaplanacanalpanama

Approach 1: Two Pointers Approach

The most efficient way to check if a string is a palindrome is to use the two pointers technique. We'll place one pointer at the beginning of the string and another at the end, then move them toward each other, comparing characters as we go.

If at any point the characters don't match, we know the string is not a palindrome. If the pointers meet in the middle without finding any mismatches, the string is a palindrome.

Before comparing characters, we'll need to handle non-alphanumeric characters and case sensitivity by either:

  • Pre-processing the string to remove non-alphanumeric characters and convert to lowercase
  • Skipping non-alphanumeric characters during comparison and comparing case-insensitively

Visualizing the two pointers approach:

0r
1a
2c
3e
4c
5a
6r

Start with left pointer at index 0 and right pointer at index 6. Compare characters and move pointers inward.

Algorithm:

  1. Initialize two pointers: left at the start of the string and right at the end of the string.
  2. While left < right, do the following:
  3. Skip non-alphanumeric characters by incrementing left or decrementing right as needed.
  4. Compare the characters at left and right positions (case-insensitively).
  5. If they don&apos;t match, return false.
  6. If they match, move the pointers toward each other (increment left, decrement right).
  7. If the loop completes without returning false, return true (the string is a palindrome).

Time Complexity:

O(n)

We traverse the string once, where n is the length of the string.

Space Complexity:

O(1)

We use a constant amount of extra space regardless of input size.

Approach 2: Reverse and Compare Approach

Another approach is to create a cleaned version of the string (removing non-alphanumeric characters and converting to lowercase), then reverse it and compare with the original cleaned string.

If the reversed string matches the original cleaned string, then the input is a palindrome.

Algorithm:

  1. Create a cleaned version of the string by removing non-alphanumeric characters and converting to lowercase.
  2. Create a reversed version of the cleaned string.
  3. Compare the cleaned string with its reversed version.
  4. If they match, return true (the string is a palindrome). Otherwise, return false.

Time Complexity:

O(n)

We process each character in the string once to clean it and once to reverse it.

Space Complexity:

O(n)

We create new strings for the cleaned and reversed versions, each of which could be up to n characters long.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function isPalindrome(s):
    // Initialize pointers
    left = 0
    right = s.length - 1
 
    while left < right:
        // Skip non-alphanumeric characters from left
        while left < right and !isAlphanumeric(s[left]):
            left++
 
        // Skip non-alphanumeric characters from right
        while left < right and !isAlphanumeric(s[right]):
            right--
 
        // Compare characters (case-insensitive)
        if toLowerCase(s[left]) != toLowerCase(s[right]):
            return false
 
        // Move pointers toward each other
        left++
        right--
 
    // If we get here, the string is a palindrome
    return true
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone