Palindrome Check

🧩 Problem Statement

Write a function that checks whether a given string is a palindrome — a string that reads the same backward as forward.

---

✍️ Function Signature

public boolean isPalindrome(String s)

---

🚀 Approaches

🧠 1. Two-Pointer Technique (Most Efficient)

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) {
            return false;
        }
    }
    return true;
}

• Time Complexity: O(n)
• Space Complexity: O(1)
• ✅ Best for performance-sensitive applications.

---

🔁 2. Manual Reverse Comparison

public boolean isPalindrome(String s) {
    String reversed = "";
    for (int i = s.length() - 1; i >= 0; i--) {
        reversed += s.charAt(i);
    }
    return s.equals(reversed);
}

• Time Complexity: O(n²) due to string concatenation.
• Space Complexity: O(n)
• ❗ Not recommended for large strings due to performance cost.

---

🧱 3. Using Stack

import java.util.Stack;

public boolean isPalindrome(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        stack.push(c);
    }
    for (char c : s.toCharArray()) {
        if (c != stack.pop()) {
            return false;
        }
    }
    return true;
}

• Time Complexity: O(n)
• Space Complexity: O(n)
• 🧰 Useful if stack-based structure is required.

---

🧮 4. Recursive Check

public boolean isPalindrome(String s) {
    return isPalHelper(s, 0, s.length() - 1);
}

private boolean isPalHelper(String s, int left, int right) {
    if (left >= right) return true;
    if (s.charAt(left) != s.charAt(right)) return false;
    return isPalHelper(s, left + 1, right - 1);
}

• Time Complexity: O(n)
• Space Complexity: O(n) due to call stack.
• 💡 Elegant, but not optimal for very large strings.

---

🧪 Test Cases

public class PalindromeCheckTest {
    public static void main(String[] args) {
        test("madam", true);
        test("racecar", true);
        test("apple", false);
        test("A", true);
        test("", true);
        test("level", true);
        test("deified", true);
        test("abcba", true);
        test("abccba", true);
        test("abcdef", false);
    }

    private static void test(String input, boolean expected) {
        PalindromeSolver solver = new PalindromeSolver();
        boolean result = solver.isPalindrome(input);
        System.out.println("Input: " + input);
        System.out.println("Output: " + result);
        System.out.println("Expected: " + expected);
        System.out.println(result == expected ? "✅ Passed" : "❌ Failed");
        System.out.println("-----------------------------");
    }
}

---

📝 Notes

• Case-sensitive: "Madam" ≠ "madam" → consider using toLowerCase() if case-insensitive check is desired.
• Ignore non-alphanumeric characters: Use Character.isLetterOrDigit(c) and Character.toLowerCase(c) if required.
• Best Practice: Use the Two-Pointer Approach for most real-world applications due to its efficiency.

---

🧰 Optional Enhancement (Clean and Normalize)

public boolean isPalindrome(String s) {
    s = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) {
            return false;
        }
    }
    return true;
}

• ✅ Ignores special characters and case.
• 🔐 Suitable for checking real-world inputs like "A man, a plan, a canal: Panama".