Strings - Valid Palindrome

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.

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

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

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 * 10⁵
s consists only of printable ASCII characters.

Solution 1 - Using two pointers approach

In this approach, we will use two pointers start to point beginning of the string and end to point at the end of string, and check whether the string s has palindrome properties or not.

Implementation steps:

We will first initialize two variables start = 0, and end = s.length() -1 , both points to left and right ends of the string s.
While start and end do not intersect each other, read the characters and check the followng:
- If left side character is not alpha-numeric : Increment start pointer and continue.
- If right side character is not alpha-numeric : Decrement end pointer and continue.
- Once above conditions are checked, then check whether left and right side characters are same or not (ignoring the case). If they are not same, then return false, otherwise increment start and decrement end to continue to next characters.

public class ValidPalindrome { static boolean isPalindrome(String s) { int start = 0; int end = s.length() -1; while(start < end) { char left = s.charAt(start); char right = s.charAt(end); if(!Character.isLetterOrDigit(left)) { start++; } else if (!Character.isLetterOrDigit(right)){ end--; } else if (Character.toLowerCase(left) != Character.toLowerCase(right)) { return false; } else { start++; end--; } } return true; } public static void main(String[] args) { System.out.println(isPalindrome("A man, a plan, a canal: Panama")); System.out.println(isPalindrome("race a car")); System.out.println(isPalindrome(" ")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string length.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: