Valid Palindrome Solution for Capgemini

Company: Capgemini · Difficulty: Easy · Topics: String, Two Pointers

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.

Examples

Example 1:

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: After cleaning: "amanaplanacanalpanama" which reads the same forward and backward.

Example 2:

Input: s = "race a car"

Output: false

Explanation: After cleaning: "raceacar" which is not a palindrome.

Example 3:

Input: s = " "

Output: true

Explanation: After cleaning: "" (empty string) which is a palindrome.

Example 4:

Input: s = "0P"

Output: false

Explanation: After cleaning: "0p" which is not a palindrome.

Intuition

The key insight is to use two pointers approach after cleaning the string:

1. Convert to lowercase and remove non-alphanumeric characters

2. Use two pointers (left and right) to compare characters from both ends

3. Move inward until pointers meet, checking if characters match

Approach

Approach 1: Two Pointers with Cleaning (Optimal)

1. Convert string to lowercase

2. Remove all non-alphanumeric characters

3. Use two pointers to compare from both ends

4. Return true if all characters match, false otherwise

Approach 2: Two Pointers In-place

1. Use two pointers without cleaning the string

2. Skip non-alphanumeric characters during comparison

3. Compare only alphanumeric characters

Approach 3: Reverse and Compare

1. Clean the string (lowercase + alphanumeric only)

2. Create a reversed version

3. Compare original and reversed strings

Dry Run

Let's trace through Example 1: s = "A man, a plan, a canal: Panama"

Two Pointers with Cleaning:

• After cleaning: "amanaplanacanalpanama"
• left = 0, right = 19
• s[left] = 'a', s[right] = 'a' ✓
• left = 1, right = 18
• s[left] = 'm', s[right] = 'm' ✓
• Continue until left >= right
• All characters match ✓

Two Pointers In-place:

• left = 0, right = 26
• s[left] = 'A' (alphanumeric), s[right] = 'a' (alphanumeric)
• Convert to lowercase: 'a' == 'a' ✓
• left = 1, right = 25
• s[left] = ' ' (skip), left = 2
• s[left] = 'm', s[right] = 'm' ✓
• Continue until left >= right

Key Insights

1. Case Insensitive: Convert to lowercase before comparison

2. Alphanumeric Only: Ignore spaces, punctuation, etc.

3. Two Pointers: Efficient O(n) comparison

4. Edge Cases: Empty string, single character, all non-alphanumeric

Edge Cases

1. Empty string: Return true

2. Single character: Return true

3. All non-alphanumeric: Return true (empty after cleaning)

4. Mixed case: "RaceCar" should return true

5. Numbers: "12321" should return true

More Capgemini coding questions