125. Valid Palindrome - LeetCode Fastest Solution

Hello Code Recipian! Welcome to back to another article on LeetCode problem solutions. Today we will be solving LeetCode problem 125. Valid Palindrome.

Let's dive into the problem statement.

Problem Statement: Valid Palindrome

Given a string s, return true if it is a palindrome, otherwise return false.

A given sentence is a palindrome if, after converting all upper case letters into lowercase and after removing all the non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Example 1:

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

Example 2:

Input: sentence = "No lemon, no melon!"
Output: true
Explanation: "nolemonnomelon" is a palindrome.

Example 3:

Input: sentence = "Never odd or even."
Output: true
Explanation: "neveroddoreven" is a palindrome.

Constraints:

• 1 <= s.length <= 2 * 10^5

• s consists only of printable ASCII characters.

Solution

This problem can be efficiently solved using the two pointer technique. The idea is to use two pointers, one pointing to the start and one to the end, compare the characters and move the pointers inwards in each iteration. If all characters match then it is a palindrome, otherwise it is not.

Let's see how this works in detail.

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Initialization:

   Initialize two variables: start, end.

   1. start is the index variable used to iterate the string from the start. start is initialized to 0 to point to the first element in the string s.

   2. end is the index variable used to iterate the string from the end. end is initialized to the index of the last element in the string s.

2. Compare start and end characters: We use the start and end variables to iterate through s. In each iteration, we perform the following steps:

   1. As long as the current character pointed by start is not an alphanumeric character, ignore the current character, increment start.

   2. As long as the current character pointed by end is not an alphanumeric character, ignore the current character, decrement end.

   3. At the end of step a and b, both start and end will be pointing to a alphanumeric character. Convert both these characters to lower case and compare the characters pointed by start and end.

      1. If they are matching, continue iterating.

      2. If they are not matching, the given string s is not a palindrome. Therefore, straightaway return false as your result.

3. Return result: If the execution comes out of the main loop after iterating through all the characters in the string s, that means s reads same forward and backward and it is a palindrome. Therefore, return result as true.

Simulation

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Complexity Analysis

Time Complexity

Even through we make use of nested loops, if you observe carefully we process each character in string s only once.

If n is the length of the string s, in the worst case, when the given string is a palindrome, we end up iterating through all the characters of the string s. Thus the time complexity of this algorithm is O(n).

Space Complexity

The algorithm uses couple of extra variables start, end for its operation, these variables only use constant extra space. Hence, the space complexity of the algorithm is O(1).

That brings us to the end of this article. We appreciate the time you have taken to read through it. If you have any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to bring out more such articles in future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.