Check Whether The Given String Is A Palindrome Or Not In C

A palindrome is a sequence of characters that reads the same forwards and backward. Checking if a given string is a palindrome is a common programming challenge that tests understanding of string manipulation and algorithmic thinking. In this article, you will learn how to determine if a string is a palindrome using C programming, exploring different efficient approaches.

Problem Statement

The core problem is to write a C function that takes a string as input and returns true (or 1) if the string is a palindrome, and false (or 0) otherwise. This requires comparing characters from the beginning and end of the string, moving inwards, to ensure they match at each step.

Example

Consider the following strings:

• "madam": This string reads "madam" forward and "madam" backward, so it is a palindrome.
• "racecar": This string reads "racecar" forward and "racecar" backward, so it is a palindrome.
• "hello": This string reads "hello" forward but "olleh" backward, so it is not a palindrome.
• "A": This single-character string is a palindrome.
• "" (empty string): An empty string is typically considered a palindrome.

Background & Knowledge Prerequisites

To understand and implement the solutions, readers should be familiar with:

• C Basics: Variables, data types, loops (for, while), conditional statements (if-else).
• Character Arrays and Strings: How strings are represented in C as null-terminated character arrays.
• Pointers: Basic understanding of pointer arithmetic (optional but helpful for some string operations).
• Standard Library Functions: Especially those from like strlen() for getting string length.

Required Headers: For string manipulation and input/output, the following headers are typically needed:

#include <stdio.h>  // For printf and other standard I/O functions
#include <string.h> // For strlen function

Use Cases or Case Studies

Identifying palindromes has several practical and educational applications:

• Text Processing and Linguistics: Analyzing natural language for patterns, wordplay, or specific structures.
• Algorithm Challenges and Interviews: A frequent problem used to assess a candidate's grasp of basic algorithms and string manipulation.
• Data Validation: In certain contexts, ensuring input data follows a palindromic pattern (though less common than other validation types).
• Educational Tool: A great exercise for learning about string indexing, loops, and conditional logic.
• Cryptography (Conceptual): While not directly used in modern cryptography, the idea of symmetry and reversibility can be an initial thought process for some concepts.

Solution Approaches

Here, we will explore two common and effective approaches to check if a string is a palindrome.

Approach 1: Two Pointers (Iterative)

This is the most efficient and widely used method. It involves using two pointers, one starting from the beginning of the string and the other from the end, and moving them towards the center while comparing characters.

One-line summary: Compare characters from both ends of the string inwards using two pointers until they meet or a mismatch is found.

// Palindrome Check using Two Pointers
#include <stdio.h>
#include <string.h> // Required for strlen()

// Function to check if a string is a palindrome
// Returns 1 if palindrome, 0 otherwise
int isPalindromeTwoPointers(const char *str) {
    // Step 1: Handle null or empty string
    if (str == NULL || strlen(str) == 0) {
        return 1; // Empty string is considered a palindrome
    }

    // Step 2: Initialize two pointers
    int left = 0;
    int right = strlen(str) - 1;

    // Step 3: Iterate while left pointer is less than right pointer
    while (left < right) {
        // Step 4: Compare characters at current pointers
        if (str[left] != str[right]) {
            return 0; // Mismatch found, not a palindrome
        }
        // Step 5: Move pointers towards the center
        left++;
        right--;
    }

    // Step 6: If loop completes, string is a palindrome
    return 1;
}

int main() {
    char str1[] = "madam";
    char str2[] = "racecar";
    char str3[] = "hello";
    char str4[] = ""; // Empty string
    char str5[] = "a"; // Single character string
    char str6[] = "Madam"; // Case sensitive example

    printf("'%s' is a palindrome: %d\\n", str1, isPalindromeTwoPointers(str1));
    printf("'%s' is a palindrome: %d\\n", str2, isPalindromeTwoPointers(str2));
    printf("'%s' is a palindrome: %d\\n", str3, isPalindromeTwoPointers(str3));
    printf("'%s' is a palindrome: %d\\n", str4, isPalindromeTwoPointers(str4));
    printf("'%s' is a palindrome: %d\\n", str5, isPalindromeTwoPointers(str5));
    printf("'%s' is a palindrome: %d\\n", str6, isPalindromeTwoPointers(str6)); // Will be 0 due to case sensitivity

    return 0;
}

Run

Sample Output:

'madam' is a palindrome: 1
'racecar' is a palindrome: 1
'hello' is a palindrome: 0
'' is a palindrome: 1
'a' is a palindrome: 1
'Madam' is a palindrome: 0

Stepwise Explanation:

1. Handle Edge Cases: First, check if the input string is NULL or empty. An empty string is typically considered a palindrome.
2. Initialize Pointers: Two integer variables, left and right, are initialized. left points to the first character (index 0), and right points to the last character (strlen(str) - 1).
3. Iterate and Compare: A while loop continues as long as left is less than right. This ensures characters are compared from the outside inwards.
4. Character Check: Inside the loop, str[left] and str[right] are compared. If they are not equal, the string is not a palindrome, and the function immediately returns 0.
5. Move Pointers: If the characters match, left is incremented, and right is decremented, moving both pointers one step closer to the center of the string.
6. Return Result: If the loop completes without finding any mismatches, it means all corresponding characters matched, and the string is a palindrome. The function returns 1.

Approach 2: Reversing the String and Comparing

This approach involves creating a reversed copy of the original string and then comparing the original with its reversed version.

One-line summary: Create a reversed copy of the string and compare it character by character with the original string.

// Palindrome Check by Reversing String
#include <stdio.h>
#include <string.h> // Required for strlen(), strcpy(), strcmp()

// Function to check if a string is a palindrome
// Returns 1 if palindrome, 0 otherwise
int isPalindromeReverse(const char *str) {
    // Step 1: Handle null or empty string
    if (str == NULL || strlen(str) == 0) {
        return 1; // Empty string is considered a palindrome
    }

    // Step 2: Get the length of the original string
    int length = strlen(str);

    // Step 3: Create a buffer for the reversed string
    // +1 for the null terminator
    char reversed_str[length + 1];

    // Step 4: Reverse the string
    int i, j;
    for (i = 0, j = length - 1; i < length; i++, j--) {
        reversed_str[i] = str[j];
    }
    reversed_str[length] = '\\0'; // Null-terminate the reversed string

    // Step 5: Compare the original string with the reversed string
    // strcmp returns 0 if strings are identical
    if (strcmp(str, reversed_str) == 0) {
        return 1; // Strings are identical, so it's a palindrome
    } else {
        return 0; // Strings are different
    }
}

int main() {
    char str1[] = "madam";
    char str2[] = "racecar";
    char str3[] = "hello";
    char str4[] = ""; // Empty string
    char str5[] = "a"; // Single character string
    char str6[] = "Madam"; // Case sensitive example

    printf("'%s' is a palindrome: %d\\n", str1, isPalindromeReverse(str1));
    printf("'%s' is a palindrome: %d\\n", str2, isPalindromeReverse(str2));
    printf("'%s' is a palindrome: %d\\n", str3, isPalindromeReverse(str3));
    printf("'%s' is a palindrome: %d\\n", str4, isPalindromeReverse(str4));
    printf("'%s' is a palindrome: %d\\n", str5, isPalindromeReverse(str5));
    printf("'%s' is a palindrome: %d\\n", str6, isPalindromeReverse(str6)); // Will be 0 due to case sensitivity

    return 0;
}

Run

Sample Output:

'madam' is a palindrome: 1
'racecar' is a palindrome: 1
'hello' is a palindrome: 0
'' is a palindrome: 1
'a' is a palindrome: 1
'Madam' is a palindrome: 0

Stepwise Explanation:

1. Handle Edge Cases: Similar to the first approach, check for NULL or empty strings.
2. Get Length: Determine the length of the input string using strlen().
3. Allocate Reversed String: Declare a character array reversed_str with enough space to hold the reversed string plus a null terminator.
4. Reverse String: Iterate through the original string from start to end (using i) and copy characters into reversed_str from end to start (using j). Ensure the reversed_str is null-terminated.
5. Compare Strings: Use the strcmp() function from to compare the original string str with the reversed_str. strcmp() returns 0 if the strings are identical.
6. Return Result: Based on the strcmp() result, return 1 for a palindrome or 0 otherwise.

Conclusion

Checking for palindromes in C can be achieved effectively using different strategies. The two-pointer approach is generally preferred due to its efficiency in terms of both time complexity (O(N/2), which simplifies to O(N)) and space complexity (O(1), as it doesn't require extra storage for a reversed string). The string reversal approach is also valid but uses O(N) extra space. Both methods provide clear and understandable ways to solve this classic string manipulation problem.

Summary

• A palindrome reads the same forwards and backward.
• Two-Pointer Approach:
• Uses left and right pointers moving inwards.
• Compares characters at str[left] and str[right].
• Time Complexity: O(N)
• Space Complexity: O(1)
• String Reversal Approach:
• Creates a new string that is the reverse of the original.
• Compares the original string with the reversed copy using strcmp().
• Time Complexity: O(N) (for reversal and comparison)
• Space Complexity: O(N) (for the reversed string)
• Both approaches handle empty strings as palindromes and are case-sensitive by default.
• The two-pointer method is generally more efficient for palindrome checks.