Recent Posts

Palindrome string in C++

Written by

studymite

Check string is Palindrome Problem

A palindrome is a string that, when reversed, is the same as the original string. In the above example of reversing a string, we see two strings:

  1. FACE
  2. MADAM

On reversing the strings, we get FACE as ECAF while MADAM stays unaffected by reversal. Thus, MADAM is a palindrome.

Similarly, we have different strings like RADAR, ANNA and LEVEL. We can also have multiple WORD palindromes like

  • My gym
  • Red rum, sir, is murder
  • Step on no pets

So, how to solve this problem. Firstly, keep your IDE closed, and pick up a copy and a pen to write down the pseudo-code. For solving this problem, we have two approaches

# APPROACH 1: Brute Force

Yes, Let’s get down to brass tacks. Simply put, this will have three steps.

Pseudo Code:

  1. Store the input string.
  2. Iterate over the string backwards using a loop.
  3. Compare each character of the input string with the corresponding character in the reversed string.
  4. If all characters are equal, the input string is a palindrome. Otherwise, it is not a palindrome.

This is the easiest solution possible. We are calculating the entire possibility of reversal of string and then comparing it. The code will go like this:

Code:

#include <iostream>
#include <string.h>
using namespace std;

int main() {
   char string1[20], stringReversed[20];
   int i, length, j;
   int flag = 0;

   cout << "Enter a string: ";
   cin >> string1;

   length = strlen(string1);

   for (i = length - 1, j = 0; i >= 0, j < length; i--, j++) {
      stringReversed[j] = string1;
   }

   for (i = 0; i < length; i++) {
      if (string1[i] != stringReversed[i]) {
         flag = 1;
         break;
      }
   }

   if (flag) {
      cout << string1 << " is not a palindrome" << endl;
   } else {
      cout << string1 << " is a palindrome" << endl;
   }

   return 0;
}

We first reverse the string by using two variables, I which starts from the front and j which starts from the back. This reversal is then completed, after which we evaluate if the strings are equal or not.

The runtime of this solution is O(n), which means that the time it takes to execute the algorithm is directly proportional to the size of the input string. As the size of the string increases, the runtime also increases.

# APPROACH 2: Optimized Solution

In the above approach, what if instead of iterating the whole string and then using another loop to compare, we only iterate half a string and compare in the same loop? Since we know that the first half will be equal to second half in a palindrome, we use this as the improvement while devising our second algorithm.

Pseudo Code:

  1. Store the input string.
  2. Initialize two variables, one at the start of the string and the other at the end.
  3. Iterate over the string, comparing the characters at the start and end variables at each iteration.
  4. If all iterations are passed and the characters are equal, the input string is a palindrome. Otherwise, it is not a palindrome.

Code:

The runtime of this solution is O(n/2), as we only need to loop through half of the string. This reduces the number of iterations and results in a more efficient solution.

#include <iostream>
#include <string.h>
using namespace std;

int main() {
   char string1[20];
   int i, length;
   int flag = 0;

   cout << "Enter a string: ";
   cin >> string1;

   length = strlen(string1);

   for (i = 0; i < length; i++) {
      if (string1[i] != string1[length - i - 1]) {
         flag = 1;
         break;
      }
   }

   if (flag) {
      cout << string1 << " is not a palindrome" << endl;
   } else {
      cout << string1 << " is a palindrome" << endl;
   }

   return 0;
}

This is how we solve the check palindrome problem.

Palindrome string in C++