Valid Palindrome and LeetCode Solution in Java: A Detailed Guide

Introduction

Palindrome-related problems are a common occurrence in coding interviews and competitive programming. They test your ability to work with strings and often require clever solutions to efficiently determine whether a given string is a palindrome. In this blog post, we’ll explore the concept of a valid palindrome, discuss the problem statement for LeetCode’s “Valid Palindrome” (Problem #125), and provide a step-by-step solution in Java. We’ll use simple language and examples to help you understand the problem and its solution thoroughly.

Table of Contents

1. What is a Palindrome?
2. Problem Statement: LeetCode #125 – Valid Palindrome
3. Approach to Solve the Problem
4. Implementation in Java
5. Testing and Examples
6. Time and Space Complexity Analysis
7. Conclusion

---

1. What is a Palindrome?

A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward. For example, “racecar,” “level,” and “12321” are all palindromes. Palindromes are intriguing because they have a unique property that allows them to remain the same when reversed.

2. Problem Statement: LeetCode #125 – Valid Palindrome

Problem Statement:

Given a string s, determine if it is a valid palindrome. A valid palindrome is a string that reads the same forward and backward, ignoring non-alphanumeric characters and considering uppercase and lowercase characters as equivalent.

Examples:

1. Input: s = "A man, a plan, a canal: Panama", Output: true
2. Input: s = "race a car", Output: false
3. Input: s = "ab_a", Output: true

In this problem, you need to check if the input string is a valid palindrome, considering only alphanumeric characters and ignoring case.

3. Approach to Solve the Problem

To solve this problem, we’ll use a two-pointer approach. Here’s a step-by-step explanation of the approach:

1. Preprocessing: First, we need to preprocess the input string to remove non-alphanumeric characters and convert all characters to lowercase. This preprocessing step is essential to ensure that we only compare alphanumeric characters and consider uppercase and lowercase characters as equivalent.
2. Two-Pointer Comparison: After preprocessing, we’ll use two pointers, one starting from the beginning of the string (left) and the other starting from the end of the string (right). We’ll compare the characters at these positions while moving the pointers towards each other.
3. Character Comparison: At each step, we’ll compare the characters at the left and right pointers. If they match, we continue moving the pointers towards each other. If they don’t match, we can immediately conclude that the string is not a valid palindrome and return false.
4. Termination Condition: We repeat the character comparison and pointer movement until the left pointer is less than or equal to the right pointer. If we successfully compare all characters without finding a mismatch, we can conclude that the string is a valid palindrome and return true.

4. Implementation in Java

Let’s now implement the approach discussed above in Java. We’ll provide a detailed code snippet with comments for better understanding:

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

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

        // Character comparison and pointer movement
        while (left < right) {
            // Compare characters at the left and right pointers
            if (s.charAt(left) != s.charAt(right)) {
                return false; // Mismatch found, not a palindrome
            }

            // Move the pointers towards each other
            left++;
            right--;
        }

        // All characters matched, it's a valid palindrome
        return true;
    }
}

5. Testing and Examples

Let’s test our solution with some example inputs to ensure it works correctly:

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test Cases
        System.out.println(solution.isPalindrome("A man, a plan, a canal: Panama")); // true
        System.out.println(solution.isPalindrome("race a car")); // false
        System.out.println(solution.isPalindrome("ab_a")); // true
    }
}

When you run the code above, you should see the following output, which matches the expected results for the given test cases:

true
false
true

6. Time and Space Complexity Analysis

Let’s analyze the time and space complexity of our solution:

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input string s. This is because we iterate through the string once to preprocess it and then use two pointers that move towards each other, comparing characters in O(1) time for each comparison.

Space Complexity:

The space complexity is O(n) as well. This is primarily due to the space used for the preprocessed string s, which can be as large as the input string itself.

7. Conclusion

In this blog post, we explored the concept of palindromes and discussed the problem of determining whether a given string is a valid palindrome, as presented in LeetCode problem #125. We introduced a two-pointer approach and provided a detailed Java implementation with explanations.

By following this approach and understanding the underlying concepts, you should now be better prepared to solve similar problems that involve string manipulation and pattern matching in coding interviews and competitive programming. Palindrome problems, such as the one we discussed here, are not only a great way to improve your algorithmic skills but also a testament to the elegance of problem-solving in computer science. Happy coding!

Thank You!

Read More –

Contains Duplicate LeetCode Solution in Java | Leet code Must Do Questions | Code with Kamlesh – https://kamleshsingad.com/contains-duplicate-leetcode-solution-in-java/

Two Sum II – Input Array Is Sorted | Two Sum II – Input Array Is Sorted LeetCode Solution in Java – https://kamleshsingad.com/two-sum-ii-input-array-is-sorted-leetcode-solution-in-java/

234. Palindrome Linked List | Palindromic Linked List LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/234-palindrome-linked-list-and-leetcode-solution-in-java/