LeetCode #125 - Valid Palindrome Solution in Java

 Problem Statement:

A string is a valid palindrome if it reads the same forwards and backwards, ignoring spaces, punctuation, and cases. The challenge is to write a program that determines if a given string is a valid palindrome.

In this article, we’ll explore the Java solution for LeetCode problem #125, discuss how we can clean the string, and apply a two-pointer approach to check for palindromes efficiently.

Understanding the Problem

A palindrome is a word, phrase, or sequence that reads the same backward as forward, after ignoring non-alphanumeric characters and case differences. For example:

• "A man, a plan, a canal: Panama" is a valid palindrome.
• "race a car" is not a palindrome.

We need to handle strings with spaces, punctuation, and mixed cases while ensuring the palindrome check is efficient.

Solution Approach

We’ll take a few steps to solve the problem:

1. Clean the String: Remove all non-alphanumeric characters (like punctuation and spaces) and convert everything to lowercase.
2. Two-Pointer Technique: Use two pointers starting at the beginning and end of the cleaned string, comparing characters to check if they match.
3. Handle Edge Cases: Consider edge cases like empty strings and single-character strings.

Let’s jump into the Java solution.

public class IsValidPalindrome {

public static void main(String[] args) {

String s = "A man, a plan, a canal: Panama!";

boolean b = checkIfAValidPalindrome(s);

System.out.println(b);

}

private static boolean checkIfAValidPalindrome(String s) {

if(s.length()==0) {

throw new IllegalArgumentException("Empty String!");

}

//Clean the string, remove all the alphanumeric characters from it                  and convert to to lower case.

String cleanString = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

int start=0;

int end=cleanString.length()-1;

while (start<end) {

if (cleanString.charAt(start) !=cleanString.charAt(end)) {

return false;

}

start++;

end--;

}

return true;

}

}

Explanation of the Solution

1. Cleaning the String:
   We use the replaceAll() method with a regular expression [^a-zA-Z0-9] to remove all characters that are not letters or digits. This ensures we’re only working with alphanumeric characters. The .toLowerCase() method converts everything to lowercase, so we don't need to worry about case sensitivity.

2. Two-Pointer Technique:
   After cleaning the string, we initialize two pointers:

   • One at the start (start).
   • One at the end (end).

   We then compare the characters at both pointers, moving them towards the center. If the characters don’t match, we return false. If all characters match, the string is a palindrome, and we return true.

3. Edge Case Handling:
   If the input string is empty, we consider it a valid palindrome and return true. This approach also handles single-character strings as valid palindromes.

Time and Space Complexity

• Time Complexity:
  The time complexity is O(n), where n is the length of the string. This is because we traverse the string once to clean it and then use the two-pointer approach to check for palindromes in another single pass.

• Space Complexity:
  The space complexity is O(n) since we store the cleaned version of the input string.

Why This Solution Is Efficient

• Optimal String Cleaning:
  The use of regular expressions makes it easy to remove unwanted characters in a single line of code.

• Two-Pointer Technique:
  This technique is highly efficient because it reduces the number of comparisons to just half of the string's length, ensuring the algorithm runs in linear time.

Conclusion

This solution efficiently solves the LeetCode #125 - Valid Palindrome problem using string cleaning and the two-pointer technique. It runs in O(n) time, making it optimal for large inputs.

When solving palindrome problems, always remember to handle different cases like punctuation, spaces, and case-sensitivity. By doing so, you’ll write a robust solution ready for coding interviews and competitive programming.

Tags:
#LeetCode #Java #DSA #CodingInterview #FANG #Programming #InterviewPrep #TechInterview #HIndex #CodingChallenges