The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards, e.g. "madam" or "nurses run". The following list illustrates palindrome.

"madam" – "madam"
"racecar" -  "racecar"
"22/02/2022" – "22 02 20 22"    
"nurses run" - "nur ses run"
"Ah, Satan sees Natasha" - "ah sataN sees nataS hA"
"A Toyota" - "a toyoT A"
"A Toyota's a Toyota" - "a toyoT a s a toyoT A"
"Dennis and Edna sinned" - "dennis and E dna sinned"
"Do geese see God?" - "do G ees e see g oD"
"Do nine men Interpret? Nine men I nod." - "do n I ne men iN terpret nI ne m en  i n oD"

Note that in determining if a term is a palindrome, punctuation marks including the full stop and any non-alphanumeric character, has to be ignored.

The technical definition of a palindrome is as follows: A term is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. For example:

    "A man, a plan, a canal: Panama."

becomes

   "amanaplanacanalpanama"

and can be clearly seen as a palindrome.

Decimal alphanumeric ASCII codes are in the range from 48 to 57 (inclusive), 65 to 90 (inclusive), and 97 to 122 (inclusive). So, to check if a character in a string is a non-alphanumeric character, just check if the character is not within any of these three ranges. That is considered as O(1) time, which may be ignored.

A term can be determine as a palindrome, using two-pointers.

Integer Division

n / 2 is integer division. This division discards the remainder. If the number of elements in the array is odd, say 9 for example, then the center (middle) index would be 4, whose element is not swapped. If the number of elements is even, say 8 for example, then the almost center (middle) left index would be 3, whose element has to be swapped with the almost center (middle) right element of index 4.

Determining if a Term is a Palindrome using Two-Pointers Technique

- Use two pointers (indexes), one at the beginning (left) and the other at the end (right) of the string.
- Then compare the characters at these positions. If they don't match, the string is not a palindrome, and return 0. Comparison is done for both characters, either in uppercase or lowercase. Do not forget to skip non-numeric characters.
- If they match, the pointers move towards each other (left pointer moves rightward, right pointer moves leftward), and continue checking.
- If the pointers would cross each other without finding a mismatch, the string is confirmed as a palindrome, and returns 1.
- While doing all the above, ignore non-alphanumeric characters, including the full stop and the space character.

Problem

Given a string s, return true if it is a palindrome, or false otherwise. Employ O(n) time and O(n) space. Use two-pointers technique.

Solution

The following program illustrates this (read through the code and comments):

#include 
#include 
#include  // included for tolower()

// Function to check if a string is a palindrome
bool isPalindrome(char s[], int n){
    int left = 0;
    int right = n-1;

    // Continue looping while the two pointers have not met
    while (left < right) {
        int leftCd = s[left]; 
        int rightCd = s[right]; 

        bool OKLeft = false;
        if ((leftCd>=48 && leftCd<=57) || (leftCd>=65 && leftCd<=90) || (leftCd>=97 && leftCd <= 122))
            OKLeft = true;
        bool OKRight = false;
        if ((rightCd>=48 && rightCd<=57) || (rightCd>=65 && rightCd<=90) || (rightCd>=97 && rightCd <= 122))
            OKRight = true;

        if (!OKLeft) {
            left++; // Skip non-alphanumeric on left
        } else if (!OKRight) {
            right--; // Corrected: Skip non-alphanumeric on right
        } else {
            // Both are alphanumeric, compare them (case-insensitive)
            if (tolower(s[left]) != tolower(s[right])) {    //tolower for both case sensitive comparison
                return false;
            }
            left++;
            right--;
        }
    }

    // If no mismatch is found, return 1 (palindrome)
    return true;
}

int main(){
    int n = 0;    //length (size) of string to be determined in function below
    char stri[] = "A man, a plan, a canal: Panama.";    //given string
    
    char *ptr = stri;
    while (*ptr != '\0') {    //in C a string ends with '\0', which should not be counted
        ptr++; 
        n += 1;
    }

    bool ret = isPalindrome(stri, n);
    
    printf("%i\n", ret);

    return 0;
}

The output is 1, for true.

The time complexity is actually O(2N) for both the input while-loop and the called function's while-loop. However, the coefficient (multiplier of 2) is usually omitted. The space complexity is O(N) for the input string array, which is the same as the called function's string array.

Thanks for reading.