1. Problem

A palindrome is a word, phrase, number, or sequence of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization).

Examples:

• madam
• racecar
• level

2. Steps to check if string is palindrome

Here are the steps to check if a string is a palindrome:

1. Normalize the string (Optional but necessary if case sensitivity, spaces, and punctuation don’t matter):
   – Convert the string to all lowercase (or uppercase) to ensure the comparison is case-insensitive.
   – Remove all non-alphanumeric characters (spaces, punctuation, etc.) if needed.
2. Set two pointers: One pointer at the start (left) and one at the end (right) of the string.
3. Compare characters from both ends:
   – While left < right, compare the characters at left and right indices.
   – If they are not equal, the string is not a palindrome, so return false.
   – If they are equal, move the left pointer to the right and the right pointer to the left, and continue the comparison.
4. Return true if all characters match: If all characters match during the comparisons, return true, as the string is a palindrome.
   

3. Program

public class PalindromeProblem {

    // This solution has O(N)linear running time complexity
    public boolean isPalindrome(String s) {

        int forward = 0;
        int backward = s.length()-1;

        while(forward < backward) {
            if(s.charAt(forward) != s.charAt(backward))
                return false;

            forward++;
            backward--;
        }

        return true;
    }

    public static void main(String[] args){
        String str = "madam";

        PalindromeProblem palindromeProblem = new PalindromeProblem();
        boolean isPalindrome = palindromeProblem.isPalindrome(str);

        System.out.println(isPalindrome);
    }
}