TIC
The Interns Company

Valid Palindrome

EasyAcceptance: 42.3%
Two PointersString

Problem Statement

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.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters

Input Format:

  • A string s

Output Format:

  • Return true if the string is a palindrome, false otherwise

Examples:

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:

After removing non-alphanumeric characters, s is "". Since an empty string reads the same forward and backward, it is a palindrome.

Example 4:

Input:

s = "0P"

Output:

false

Explanation:

After removing non-alphanumeric characters, s is "0p". "0p" is not a palindrome.

Solutions

Two Pointers Approach

Time: O(n)
Space: O(1)

Use two pointers to compare characters from both ends of the string, ignoring non-alphanumeric characters.

In-place Two Pointers Approach

Time: O(n)
Space: O(1)

Use two pointers without creating a new string, skipping non-alphanumeric characters as we iterate through the original string.

Reverse and Compare Approach

Time: O(n)
Space: O(n)

Clean the string, create a reversed version, and compare the two strings.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Convert to lowercase: 'a man, a plan, a canal: panama'
  2. Remove non-alphanumeric characters: 'amanaplanacanalpanama'
  3. Initialize left = 0, right = 20 (length - 1)
  4. Compare s[0] = 'a' and s[20] = 'a': match, left = 1, right = 19
  5. Compare s[1] = 'm' and s[19] = 'm': match, left = 2, right = 18
  6. Compare s[2] = 'a' and s[18] = 'a': match, left = 3, right = 17
  7. Compare s[3] = 'n' and s[17] = 'n': match, left = 4, right = 16
  8. Compare s[4] = 'a' and s[16] = 'a': match, left = 5, right = 15
  9. Compare s[5] = 'p' and s[15] = 'p': match, left = 6, right = 14
  10. Compare s[6] = 'l' and s[14] = 'l': match, left = 7, right = 13
  11. Compare s[7] = 'a' and s[13] = 'a': match, left = 8, right = 12
  12. Compare s[8] = 'n' and s[12] = 'n': match, left = 9, right = 11
  13. Compare s[9] = 'a' and s[11] = 'a': match, left = 10, right = 10
  14. left is no longer less than right, so we exit the loop
  15. Return true, as all character comparisons matched

Hints

Hint 1
Clean the string by removing non-alphanumeric characters and converting to lowercase.
Hint 2
Use two pointers, one starting from the beginning and one from the end of the string.
Hint 3
Compare the characters at the two pointers and move them towards each other.

Video Tutorial

Valid Palindrome - Two Pointers Solution

YouTube•Learn the Valid Palindrome solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the two pointers moving from opposite ends of the string and comparing characters while skipping non-alphanumeric characters.

Key visualization elements:

  • left pointer
  • right pointer
  • comparison

Similar Questions

Valid Anagram

Easy

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Asked By

FacebookMicrosoftAmazonGoogleAppleAdobeBloombergUber

Implementation Notes

This is a commonly asked interview question that tests string manipulation and two pointers technique. It's important to handle edge cases such as empty strings, strings with only spaces, and strings with special characters.