StringProblem 2 of 43
Check whether a String is Palindrome or not
Problem Statement
Given a string, check whether it is a palindrome or not. A palindrome is a string that reads the same forwards and backwards.
Example:
-
Input:
"madam" -
Output:
true(reads same forwards and backwards) -
Input:
"hello" -
Output:
false -
Input:
"A man a plan a canal Panama"(ignoring spaces and case) -
Output:
true
Approach 1: Brute Force (Reverse and Compare)
Intuition
Reverse the string and compare it with the original. If they are equal, the string is a palindrome.
Algorithm
- Create a reversed copy of the string
- Compare the original string with the reversed string
- Return true if they match, false otherwise
java
public class Solution {
public boolean isPalindrome(String s) {
String reversed = new StringBuilder(s).reverse().toString();
return s.equals(reversed);
}
// Without StringBuilder
public boolean isPalindromeBruteForce(String s) {
StringBuilder reversed = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--) {
reversed.append(s.charAt(i));
}
return s.equals(reversed.toString());
}
}Complexity Analysis
- Time Complexity: O(n) - Reversing takes O(n), comparison takes O(n)
- Space Complexity: O(n) - Extra space for reversed string
Approach 2: Optimal (Two Pointer)
Intuition
Use two pointers, one at the start and one at the end. Compare characters at both pointers and move them towards the center. If all characters match, it's a palindrome.
Algorithm
- Initialize
left = 0andright = n - 1 - While
left < right:- If
s[left] != s[right], return false - Increment
left, decrementright
- If
- Return true
java
public class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// Handling alphanumeric characters only
public boolean isPalindromeAlphaNumeric(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
// Skip non-alphanumeric from left
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
// Skip non-alphanumeric from right
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;
}
}Complexity Analysis
- Time Complexity: O(n) - We traverse at most n/2 pairs
- Space Complexity: O(1) - Only using constant extra space
Approach 3: Recursive
Intuition
Compare the first and last characters, then recursively check the substring without these characters.
java
public class Solution {
public boolean isPalindromeRecursive(String s, int left, int right) {
if (left >= right) {
return true;
}
if (s.charAt(left) != s.charAt(right)) {
return false;
}
return isPalindromeRecursive(s, left + 1, right - 1);
}
public boolean isPalindrome(String s) {
return isPalindromeRecursive(s, 0, s.length() - 1);
}
}Complexity Analysis
- Time Complexity: O(n) - We check at most n/2 pairs
- Space Complexity: O(n) - Recursion stack space
Key Takeaways
- Two-pointer technique is the most efficient approach for palindrome checking
- For real-world scenarios, consider handling:
- Case insensitivity (convert to lowercase)
- Non-alphanumeric characters (skip them)
- The recursive approach is clean but uses O(n) stack space
- Early termination on first mismatch makes the algorithm efficient