Scale Engineer

Valid Palindrome

Easy
#0125Time: O(N)Space: O(N)27 companies
Patterns
Two Pointers
Data structures
String
Companies
AccentureAmerican ExpressCadenceCapgemini

Prompt

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 <= s.length <= 2 * 105
  • s consists only of printable ASCII characters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves creating a new string by filtering out non-alphanumeric characters and converting all letters to lowercase. Then, this new string is compared with its reversed version to determine if it's a palindrome.

Algorithm

  1. Initialize an empty StringBuilder, let's call it filteredBuilder.
  2. Iterate through each character c of the input string s.
  3. If c is an alphanumeric character: a. Convert c to its lowercase equivalent. b. Append the lowercase character to filteredBuilder.
  4. Convert filteredBuilder to a string, filteredString.
  5. Create a new string, reversedString, which is the reverse of filteredString.
  6. Compare filteredString and reversedString. If they are equal, return true. Otherwise, return false.

Walkthrough

First, we iterate through the input string s. We use a StringBuilder to build a new string. For each character in s, we check if it's a letter or a digit using Character.isLetterOrDigit(). If it is, we convert it to lowercase using Character.toLowerCase() and append it to our StringBuilder. After iterating through the entire input string, we have a "cleaned" version. We then create a reversed version of this cleaned string. Finally, we compare the cleaned string with its reversed counterpart. If they are identical, the original string is a palindrome.

class Solution {    public boolean isPalindrome(String s) {        StringBuilder filteredString = new StringBuilder();        for (char c : s.toCharArray()) {            if (Character.isLetterOrDigit(c)) {                filteredString.append(Character.toLowerCase(c));            }        }                String original = filteredString.toString();        String reversed = filteredString.reverse().toString();                return original.equals(reversed);    }}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

  • Simple and easy to understand.

  • Separates the concerns of filtering and palindrome checking.

Cons

  • Inefficient in terms of space. It requires creating at least one, and in this specific implementation, two new strings whose size can be up to the original string's length.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem