Solving LeetCode's 'Valid Palindrome' Problem in Java

Introduction

LeetCode is a popular platform for honing your coding skills and problem-solving abilities. One of the fundamental problems you might encounter is checking whether a given string is a palindrome. In this blog post, we'll tackle the "Valid Palindrome" problem and provide a Java solution.

30-Day LeetCode Challenge

Before we dive into the problem and its solution, let's talk about the 30-Day LeetCode Challenge. Participating in this challenge can be a fantastic way to level up your coding skills. It offers a structured approach to practicing various types of problems, from easy to hard, over a month. Whether you're a beginner or an experienced coder, it's a great opportunity to sharpen your problem-solving abilities and learn new techniques.

Problem Statement

A phrase is considered a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. For example, "amanaplanacanalpanama" is a palindrome. Given a string s, your task is to determine whether it's a palindrome.

Example

Let's consider a few examples:

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: An empty string "" after removing non-alphanumeric characters is considered a palindrome.

Solution Approach

We can solve this problem efficiently by following these steps:

Remove all non-alphanumeric characters from the input string s.
Convert the cleaned string to lowercase.
Reverse the cleaned string.
Check if the cleaned string equals its reversed version. If they are equal, the input string is a palindrome; otherwise, it is not.

Java Code Implementation

Here's the Java code that implements the solution approach:

class Solution {
    public boolean isPalindrome(String s) {
        // Step 1: Remove non-alphanumeric characters and convert to lowercase
        String cleanedString = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

        // Step 2: Reverse the cleaned string
        String reversedString = new StringBuilder(cleanedString).reverse().toString();

        // Step 3: Check if the cleaned string equals its reversed version
        return cleanedString.equals(reversedString);
    }
}

Explanation

Let's break down the code into simpler terms:

We use replaceAll("[^a-zA-Z0-9]", "") to remove all non-alphanumeric characters (like spaces, punctuation) and toLowerCase() to convert the cleaned string to lowercase.
new StringBuilder(cleanedString).reverse().toString() reverses the cleaned string by creating a StringBuilder from it, reversing it and converting it back to a string.
Finally, we compare the cleaned string with its reversed version. If they are the same, the input string is a palindrome, and we return true; otherwise, we return false.

Time and Space Complexity Analysis

Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the input string s. We perform a single pass through the string to clean and check for palindromic properties.
Space Complexity: The space complexity is O(n) as well because we create two additional strings of the same length as the input string: one for the cleaned string and one for the reversed string.

Conclusion

Solving the "Valid Palindrome" problem on LeetCode is a great exercise to strengthen your string manipulation and algorithmic skills. The provided Java solution demonstrates a straightforward approach to determining whether a given string is a palindrome while explaining the code and its complexities for beginners. By participating in the 30-Day LeetCode Challenge, you can embark on a structured coding journey and enhance your problem-solving abilities. Happy coding!

Day01 : Solving LeetCode's "Valid Palindrome" Problem in Java

Table of contents