What is the time complexity of Valid Palindrome?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Valid Palindrome?

This problem uses Two Pointers, String. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Valid Palindrome?

**Decoupling Normalization and Comparison:** The solution brilliantly separates the concerns of string preparation (filtering non-alphanumeric characters and lowercasing) from the actual palindrome verification. This makes the code modular, easier to understand, and less prone to errors, as each step addresses a single, well-defined part of the problem. **Efficient Two-Pointer Symmetry Check:** Once the `new_string` is constructed, the classic two-pointer technique is employed. By using one pointer starting at the beginning (`l`) and another at the end (`r`), we can efficiently compare characters symmetrically inwards. This avoids the need to explicitly reverse the string (which would involve creating another full string copy) and allows for an in-place comparison, halting immediately upon the first mismatch.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Valid Palindrome - LeetCode 125 Solution

Q: Which companies ask LeetCode 125. Valid Palindrome in interviews?

This problem is frequently asked at Accenture, American Express, Axon, Bank of America, Cadence and 22 more companies.

Valid Palindrome - Complete Solution Guide

Valid Palindrome is LeetCode problem 125, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 . 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"

Detailed Explanation

The "Valid Palindrome" problem isn't just a straightforward check for reading the same forwards and backwards; it introduces a crucial pre-processing step that's central to its definition. Before we even begin comparing characters, we must first clean up the input string `s`. This involves two specific transformations: eliminating any characters that aren't letters or numbers (like spaces, punctuation, or symbols), and then converting all remaining letters to lowercase. Only after this meticulous sanitization process can we actually determine if the resulting sequence is a palindrome.

Solution Approach

The provided solution elegantly breaks down the problem into two distinct and manageable phases. The first phase focuses entirely on normalization: it iterates through the original input string `s`, character by character. For each character, it first checks if it's alphanumeric using `ch.isalnum()`. If it passes this test, the character is then converted to lowercase with `ch.lower()` and appended to a `new_string`. This `new_string` becomes the definitive, cleaned-up representation that perfectly aligns with the problem's criteria for a palindrome check.

Step-by-Step Algorithm

Step 1: Create a new string containing only the alphanumeric characters from the input string, converting all characters to lowercase.
Step 2: Initialize two pointers, `left` and `right`, to the start and end of the new string, respectively.
Step 3: Iterate while `left` is less than `right`. In each iteration, compare the characters at `left` and `right`.
Step 4: If the characters are different, return `false`. Otherwise, increment `left` and decrement `right`.
Step 5: If the loop completes without finding a mismatch, return `true`.

Key Insights

**Decoupling Normalization and Comparison:** The solution brilliantly separates the concerns of string preparation (filtering non-alphanumeric characters and lowercasing) from the actual palindrome verification. This makes the code modular, easier to understand, and less prone to errors, as each step addresses a single, well-defined part of the problem.
**Efficient Two-Pointer Symmetry Check:** Once the `new_string` is constructed, the classic two-pointer technique is employed. By using one pointer starting at the beginning (`l`) and another at the end (`r`), we can efficiently compare characters symmetrically inwards. This avoids the need to explicitly reverse the string (which would involve creating another full string copy) and allows for an in-place comparison, halting immediately upon the first mismatch.
**Leveraging Python's Expressive Built-ins:** Python's built-in string methods like `isalnum()` and `lower()`, combined with a generator expression and `''.join(...)`, provide an exceptionally concise and readable way to perform the string normalization. This approach expresses the intent of filtering and transforming characters very clearly without requiring verbose manual character-by-character loops for the initial cleanup.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Two Pointers, String.

Companies

Asked at: Accenture, American Express, Axon, Bank of America, Cadence, Capgemini, Cisco, EPAM Systems, Infosys, Intel, RBC, SAP, ServiceNow, Shopee, Spotify, TikTok, Tinkoff, Toast, Turing, Uber, VK, Visa, Wayfair, Wipro, Yahoo, Yandex, Zenefits.

Valid Palindrome | LeetCode 125

Easy

Two Pointers String

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

Solution Code

Available in:

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 125: Valid Palindrome - Detailed explanation and solution approaches.

Topics

Two Pointers String

Companies

AccentureAmerican ExpressAxonBank of AmericaCadenceCapgeminiCiscoEPAM Systems

Stats

Difficulty:Easy

Languages:4

Companies:27

Problem #:125

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Create a new string containing only the alphanumeric characters from the input string, converting all characters to lowercase.
2
Step 2: Initialize two pointers, `left` and `right`, to the start and end of the new string, respectively.
3
Step 3: Iterate while `left` is less than `right`. In each iteration, compare the characters at `left` and `right`.
4
Step 4: If the characters are different, return `false`. Otherwise, increment `left` and decrement `right`.
5
Step 5: If the loop completes without finding a mismatch, return `true`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The preprocessing step takes O(n) time because it iterates through each character of the string once. The two-pointer comparison also takes O(n) time in the worst case (it iterates through at most half the string). The space complexity depends on whether a new string is created. The Java, C++, and C solutions generally operate in-place or use a very limited amount of extra space making it O(1). The python solution creates a copy of the filtered string adding to the space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using String Reversal

Reverse the cleaned string and compare it to the original cleaned string. If they are equal, it's a palindrome.

Time: O(n)Space: O(n) for storing the reversed string.

Trade-offs: This approach is less efficient in terms of space complexity than the two-pointer approach, especially for very large strings. The two-pointer approach is generally preferred for its better space efficiency.

✨

Key Insights

1**Decoupling Normalization and Comparison:** The solution brilliantly separates the concerns of string preparation (filtering non-alphanumeric characters and lowercasing) from the actual palindrome verification. This makes the code modular, easier to understand, and less prone to errors, as each step addresses a single, well-defined part of the problem.
2**Efficient Two-Pointer Symmetry Check:** Once the `new_string` is constructed, the classic two-pointer technique is employed. By using one pointer starting at the beginning (`l`) and another at the end (`r`), we can efficiently compare characters symmetrically inwards. This avoids the need to explicitly reverse the string (which would involve creating another full string copy) and allows for an in-place comparison, halting immediately upon the first mismatch.
3**Leveraging Python's Expressive Built-ins:** Python's built-in string methods like `isalnum()` and `lower()`, combined with a generator expression and `''.join(...)`, provide an exceptionally concise and readable way to perform the string normalization. This approach expresses the intent of filtering and transforming characters very clearly without requiring verbose manual character-by-character loops for the initial cleanup.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string (""). The solution correctly handles this case by returning `true` because an empty string is a palindrome.
Edge case 2: String with only non-alphanumeric characters. The solution correctly handles this by cleaning the string, resulting in an empty string and returning `true`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle non-alphanumeric characters. Directly comparing characters without cleaning the string will lead to incorrect results.

✗Common mistake 2: Not converting characters to lowercase. Case sensitivity can lead to incorrect palindrome detection ('A' != 'a').

✗Common mistake 3: Off-by-one errors in pointer manipulation can lead to incorrect comparisons and infinite loops.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting palindromic sequences in biological data (DNA, RNA).

🏦Real-world scenario 2: Checking for palindromic patterns in text processing and natural language processing tasks (e.g., identifying palindromic words or phrases).

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The two-pointer technique is powerful for sorted arrays. The key insight is recognizing when elements can be processed from both ends simultaneously.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

The most common mistake is not handling the case when pointers meet. Always consider the termination condition.

👨‍💻 From Experience

This is one of the first problems I solved when learning Two Pointers. It's a great foundation for more complex problems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 4, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 30

❓

Frequently Asked Questions

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Valid Palindrome"?

For this easy-level Two Pointers problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?