String Palindrome Program in C

String Palindrome Program in C: A palindrome is a word, phrase or sentence that reads the same backward or forward. A string is said to be a palindromic string when we traverse it from start to end or end to start then we get the same result.

Examples: ada, malayalam, racecar, mom, etc.

In simple words, A string is said to be palindrome if the reverse of the string is the same as the
string.

Examples:

Let us take a few examples to understand the problem.

Example 1:

Input: String = “ABEEBA”
Output: ABEEBA is a Palindrome
Explanation: The reverse of the given string is equal to the (ABEEBA) is equal to the given string. Therefore, the given string is a palindromic string.

advertisement
advertisement

Example 2:

Input: String = “SANFOUNDRY”
Output: SANFOUNDRY is not a Palindrome
Explanation: The reverse of the given string is equal to the (YRDNUOFNAS) which is not equal to the given string. Therefore, the given string is not a palindromic string.

Problem Description

Write a C program that accepts a string and checks whether a given string is a palindrome or not.

Problem Solution

1. Take a string as input and store it in the array.
2. Reverse the string and store it in another array.
3. Compare both the arrays.

Note: Join free Sanfoundry classes at Telegram or Youtube

There are several ways to check whether a string is Palindrome or not in C. Let’s look at all different approaches to program this function:

Method 1: String Palindrome Program in C using For Loop

In this approach, we will check whether given string is palindrome or not using for loop.

Program/Source Code

Here is source code of the C program to check a given string is palindrome using for loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1.  
  2. /*
  3.  * C program to read a string and check if it's a palindrome, without
  4.  * using library functions. Display the result.
  5.  */
  6.  
  7. #include <stdio.h>
  8. #include <string.h>
  9.  
  10. void main()
  11. {
  12.     char string[25], reverse_string[25] = {'\0'};
  13.     int  i, length = 0, flag = 0;
  14.  
  15.     fflush(stdin);
  16.     printf("Enter a string: \n");
  17.     gets(string);
  18.     /*  keep going through each character of the string till its end */
  19.     for (i = 0; string[i] != '\0'; i++)
  20.     {
  21.         length++;
  22.     }
  23.     for (i = length - 1; i >= 0; i--)
  24.     {
  25.        reverse_string[length - i - 1] = string[i];
  26.     }
  27.     /*
  28.      * Compare the input string and its reverse. If both are equal
  29.      * then the input string is palindrome.
  30.      */
  31.     for (i = 0; i < length; i++)
  32.     {
  33.         if (reverse_string[i] == string[i])
  34.             flag = 1;
  35.         else
  36.             flag = 0;
  37.     }
  38.     if (flag == 1)
  39.         printf("%s is a palindrome \n", string);
  40.     else
  41.         printf("%s is not a palindrome \n", string);
  42. }
Program Explanation

1. Take a string as input and store it in the array string[].
2. Store the same string into the another array reverse_string[] in the reverse fashion.
3. Using for loop compare the elements of both the arrays.
4. If all the elements of the array are same, then it is a palindrome. Otherwise it is not a palindrome.

advertisement

Time Complexity: O(n)
The above program for checking palindrome string has a time complexity of O(n) because it uses a reverse function which has a time complexity of O(N).

Space Complexity: O(n)
In the above program, space complexity is O(n), as we use another string to store the reverse of our given string.

Runtime Test Cases

Testcase 1: In this case, we enter the string “sanfoundry” as input to check whether it is a palindrome string or not.

Enter a string: sanfoundry
sanfoundry is not a palindrome

Testcase 2: In this case, we enter the string “malayalam” as input to check whether it is a palindrome string or not.

advertisement
Enter a string: malayalam
malayalam is a palindrome

Method 2: String Palindrome Program in C using Recursion

In this approach, we check whether a given string is palindrome or not using recursion.

Program/Source Code

Here is source code of the C program to check a given string is palindrome using recursion. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*  
 * C Program to Check whether a given String is Palindrome or not 
 * using Recursion
 */
 
#include <stdio.h>
#include <string.h>
 
void check(char [], int);
 
int main()
{
    char word[15];
 
    printf("Enter a word to check if it is a palindrome\n");
    scanf("%s", word);
    check(word, 0);
 
    return 0;
}
 
void check(char word[], int index)
{
    int len = strlen(word) - (index + 1);
    if (word[index] == word[len])
    {
        if (index + 1 == len || index == len)
        {
            printf("The entered word is a palindrome\n");
            return;
        }
        check(word, index + 1);
    }
    else
    {
        printf("The entered word is not a palindrome\n");
    }
}
Program Explanation

1. In this C program, we are reading the value of string using word character array variable.
2. The check() function is used to check the string is a palindrome or not. A palindrome is a word, phrase or sentence that reads the same backward or forward.
3. Compute the difference between the lengths of the word by the index variable value by increments one value.
4. Then nested-If else condition statement is used to check the value of ‘word[]’ varaible with base index as index variable value is equal to the value of ‘word[]’ with base index len variable value.
5. If the condition is true then execute if condition statement. Another if condition statement is used to check the given string is palindrome using logical OR operator.
6. Check the value of ‘index’ variable increment by 1 is equal to the value of ‘len’ variable and the value of ‘index’ variable is equal to the value of ‘len’ variable.
7. If the condition is true then execute the statement and print the entered word is a palindrome. And again call the check() function to complete the process for whole string.
8. If the condition is false, then execute the else condition statement and print the statement as the entered word is not a palindrome.

Time Complexity: O(N)
In one function call, we are doing an O(1) operation of comparing the first
and last character. Recursive call is being done for at most N/2 times. N/2 because, in a string of
length N, we are removing 2 characters in each call. Thus, the overall complexity will be O(N).

Space Complexity: O(n2)
In the above program, space complexity is O(n2).

Runtime Test Cases

Testcase 1: In this case, we enter the string “sanfoundry” as input to check whether it is a palindrome string or not.

Enter a string: program
program is not a palindrome

Testcase 2: In this case, we enter the string “malayalam” as input to check whether it is a palindrome string or not.

Enter a string: racecar
racecar is a palindrome

Method 3: String Palindrome Program in C using Naive Approach

In this approach, we make a copy of the user input character array and then comparing both. Here we define the main function and subsequently we define the isPalindromeStr(char []) function which accepts the string, reverses it and then finally checked for equality with the original string.

Program/Source Code

Here is source code of the C program to check a given string is palindrome using naive approach. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to read a string and check if it is a 
 * palindrome. Display the result.
 */
 
#include <stdio.h>
#include <string.h>
#include <strings.h>
 
void isPalindromeStr(char str[], int len)
{
    char reverse_string[32] = { '\0' };
    for (int i = len - 1; i >= 0; i--)
    {
        reverse_string[len - i - 1] = str[i];
    }
 
    /* Compare the input string and its reverse. If both are equal
     * then the input string is palindrome. */
    printf("%s reversed is %s therefore ", str, reverse_string);
 
    // strcasecmp is defined in strings.h
    if (!strcasecmp(str, reverse_string))	
        printf("%s is a palindrome. \n", str);
    else
        printf("%s is not a palindrome. \n", str);
}
 
int main(void)
{
    char str[32];
 
    puts("Enter a string : ");
 
    /* gets is depreciated in favor of fgets as fgets 
    * provides memory safety in terms of assigning the
    * variable with the maximum allowed size and from
    * the specified source, here stdin. */
 
    fgets(str, sizeof(str), stdin);
    strtok(str, "\n");
    int length = (int)strlen(str);
    isPalindromeStr(str, length);
    return 0;
}
Program Explanation

1. Take the string as input and store it in a character array.
2. Pass the string into the isPalindromeStr function.
3. Make a copy of the original string and find its reverse.
4. If the reverse and the original string are the same ignoring case then it is a palindrome string otherwise it is not.

Time and Space Complexity:
The Time complexity of the above code is O(n) while the space complexity is O(2n) = O(n).

Runtime Test Cases

Testcase 1: In this case, we enter the string “aba” as input to check whether it is a palindrome string or not.

Enter a string: aba
aba is a palindrome

Testcase 2: In this case, we enter the string “India” as input to check whether it is a palindrome string or not.

Enter a string: India
India is not a palindrome

Method 4: String Palindrome Program in C using Optimized Approach

Here we do not create a copy of the character array but rather check for the array indices in order to decide whether the string is a palindrome.

The source of the program is as follows. Here we define the main function and subsequently we define the isPalindromeStr(char []) function which accepts the string, initializes two indices, compares at the two indices through the loop.

Program/Source Code

Here is source code of the C program to check a given string is palindrome using optimized approach. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to read a string and check if it's a
 * palindrome. Display the result.
 */
 
#include <stdio.h>
#include <string.h>
#include <ctype.h>
 
void isPalindromeStr(char str[])
{
    int pt1 = 0;
    int pt2 = (int)strlen(str) - 1;
 
    while (pt2 > pt1)
    {
        if (tolower(str[pt1++]) != tolower(str[pt2--]))	
        {
            printf("%s is not a palindrome.\n", str);
            return;
        }
    }
    printf("%s is a palindrome.\n", str);
}
 
int main(void)
{
    char str[32];
    puts("Enter a string : ");
    /* gets is depreciated in favor of fgets as fgets
     * provides memory safety in terms of assigning the
     * variable with the maximum allowed size and from
     * the specified source, here stdin. */
 
    fgets(str, sizeof(str), stdin);
    strtok(str, "\n");
    isPalindromeStr(str);
    return 0;
}
Program Explanation

1. Take the string as input and store it in a character array.
2. Pass the string into the isPalindromeStr function.
3. Define index pointers (not literal) pt1 and pt2.
4. Over the course of this program, pt1 will increase and vice versa until they become equal or in other words, reach the mid.
5. Check whether the characters at indices pt1 and pt2 are unequal for every iteration of the loop and if they are unequal, print not palindrome and return to the main function.
6. Even if this condition fails only once, the inner code gets executed and the control goes back to the main function.

Time and Space Complexity:
The Time complexity of the palindrome program is O(n) while the space complexity is also O(n).

Runtime Test Cases

Testcase 1: In this case, we enter the string “aba” as input to check whether it is a palindrome string or not.

Enter a string: malayalam
malayalam is a palindrome

Testcase 2: In this case, we enter the string “India” as input to check whether it is a palindrome string or not.

Enter a string: Sanfoundry
Sanfoundry is not a palindrome

Method 5: String Palindrome Program in C using Stack

In this approach, we identify whether the string is palindrome or not using stack.

Approach:

1. Take a string as input.
2. Store the string in the stack array.
3. Check whether the string is palindrome or not.

Program/Source Code

Here is source code of the C Program to identify whether the string is palindrome or not using stack. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Identify whether the String is Palindrome or not using Stack
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #define MAX 50
  9.  
  10. int top = -1, front = 0;
  11. int stack[MAX];
  12. void push(char);
  13. void pop();
  14.  
  15. void main()
  16. {
  17.     int i, choice;
  18.     char s[MAX], b;
  19.     while (1)
  20.     {
  21.         printf("1-enter string\n2-exit\n");
  22.         printf("enter your choice\n");
  23.         scanf("%d", &choice);
  24.         switch (choice)
  25.         {
  26.         case 1:
  27.             printf("Enter the String\n");
  28.             scanf("%s", s);
  29.             for (i = 0;s[i] != '\0';i++)
  30.             {
  31.                 b = s[i];
  32.                 push(b);
  33.             }
  34.             for (i = 0;i < (strlen(s) / 2);i++)
  35.             {
  36.                 if (stack[top] == stack[front])
  37.                 {
  38.                     pop();
  39.                     front++;
  40.                 }
  41.                 else
  42.                 {
  43.                     printf("%s is not a palindrome\n", s);
  44.                     break; 
  45.                 }
  46.             }
  47.             if ((strlen(s) / 2)  =  =  front)
  48.                 printf("%s is palindrome\n",  s);
  49.             front  =  0;
  50.             top  =  -1;
  51.             break;
  52.         case 2:
  53.             exit(0);
  54.         default:
  55.             printf("enter correct choice\n");
  56.         }
  57.     }
  58. }
  59.  
  60. /* to push a character into stack */
  61. void push(char a)
  62. {
  63.     top++;
  64.     stack[top]  =  a;
  65. }
  66.  
  67. /* to delete an element in stack */
  68. void pop()
  69. {
  70.     top--;
  71. }
Program Explanation

1. Take a string as input and store it in the array s[].
2. Load each character of the array s[] into the array stack[].
3. Use variables front and top to represent the last and top element of the array stack[].
4. Using for loop compare the top and last element of the array stack[]. If they are equal, then delete the top element, increment the variable front by 1 and compare again.
5. If they are not equal, then print the output as “It is not a palindrome”.
6. Compare the elements in the steps 4-5 upto the middle element of the array stack[].
7. If every characters of the array is equal, then it is a paliandrome.

Runtime Test Cases

In this case, we check whether the entered string is palindrome or not. The input we entered as a string are madam, ugesh, abccba and abdbca.

1-enter string
2-exit
enter your choice
1
Enter the String
madam
madam is palindrome
1-enter string
2-exit
enter your choice
1
Enter the String
ugesh
ugesh is not a palindrome
1-enter string
2-exit
enter your choice
1
Enter the String
abccba
abccba is palindrome
1-enter string
2-exit
enter your choice
1
Enter the String
abdbca
abdbca is not a palindrome
1-enter string
2-exit
enter your choice
2

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.