Check Whether a String Is a Palindrome

62.9k
1

Given a string, check whether the string is a palindrome or not.

A string is called a palindrome if it reads the same from left to right and right to left.

Example 1

Input: madam

Output: true

Explanation: The reverse of "madam" is "madam", which is the same as the original string, so it is a palindrome.

Example 2

Input: hello

Output: false

Explanation: The reverse of "hello" is "olleh", which is different from the original string, so it is not a palindrome.

Brute: Reverse the String

To check whether a string is a palindrome, the simplest idea is to reverse the string and compare it with the original string. Think of reading a word written on paper. First, we read it normally from left to right, and then we read it from right to left. If both readings give the same word, then the string is a palindrome. For example, "madam" reads the same from both sides, so it is a palindrome. But "hello" becomes "olleh" when read backward, so it is not a palindrome.

Algorithm

  1. Create an empty string to store the reversed string because we need a separate place to build the reverse of the original string.

  2. Start checking the original string from its last character because a reversed string is formed by reading characters from right to left.

  3. Add the current character to the reversed string because this builds the reversed string one character at a time.

  4. Move one position backward in the original string so that we can pick the previous character and continue building the reverse.

  5. Repeat this process until all characters are added to the reversed string because only then we will have the complete reversed version.

  6. Compare the original string with the reversed string because a string is palindrome only when both are exactly the same.

  7. If both strings are equal, return true because the string reads the same from left to right and right to left.

  8. Otherwise, return false because the reverse is different from the original string, so it is not a palindrome.

Dry Run

checkwhetherestringispalindrome

checkwhetherestringispalindrome


Solution

// C++ program to check if a string is palindrome
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks if the string is a palindrome.
// A palindrome reads the same both ways.
bool isPalindrome(string s) {
string reversed = "";
// Build reverse from right to left.
for (int i = s.length() - 1; i >= 0; i--) {
reversed += s[i];
}
// Same original and reverse means palindrome.
return s == reversed;
}
};
int main() {
// Driver code
string s = "madam";
Solution obj;
cout << (obj.isPalindrome(s) ? "true" : "false");
return 0;
}

Time Complexity: O(N)

Here, N is the length of the string.

We traverse the string once from right to left to build the reversed string.

So, the time complexity is:

O(N)

Space Complexity: O(N)

We create a new reversed string.

In the worst case, the reversed string stores all characters of the original string.

So, the space complexity is:

O(N)



Optimal: Two Pointer Approach

The previous approach is simple, but it creates an extra reversed string, which uses extra space. We can improve this by comparing characters directly from both ends of the string using the two pointer approach. A palindrome reads the same from both sides, so instead of reversing the whole string, we compare the first character with the last character, the second character with the second last character, and continue moving inward. Think of two students checking the same word: one starts from the left side and the other starts from the right side. At every step, both compare their characters. If all opposite characters are the same, the string is a palindrome. If even one pair is different, the string cannot be a palindrome.


Algorithm

  1. Place one pointer at the start of the string. This pointer is used to check characters from the left side of the string.

  2. Place another pointer at the end of the string. This pointer is used to check characters from the right side of the string.

  3. Compare the characters at both pointers. This is needed because in a palindrome, the first character must match the last character, the second character must match the second last character, and so on.

  4. If the characters are different, return false. This is needed because even one mismatch is enough to prove that the string is not a palindrome.

  5. If the characters are the same, move the left pointer one step forward. This helps us check the next character from the left side.

  6. Move the right pointer one step backward. This helps us check the next character from the right side.

  7. Continue this process while the left pointer is smaller than the right pointer. This is needed because we only have to compare opposite character pairs until both pointers meet or cross each other.

  8. If the loop finishes without finding any mismatch, return true. This means all opposite characters matched, so the string is a palindrome.

Dry Run

TWO-POINTER-APPROACH

TWO-POINTER-APPROACH

Solution

// C++ program to implement Check if String is Palindrome using Two Pointers
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks whether the given string is a palindrome.
// Instead of creating a reversed string, it compares characters from both ends.
bool isPalindrome(string s) {
int left = 0;
int right = s.length() - 1;
// Continue checking until both pointers meet or cross each other.
while (left < right) {
// If characters at opposite ends are different, the string cannot be a palindrome.
if (s[left] != s[right]) {
return false;
}
// Move both pointers toward the middle after a successful match.
left++;
right--;
}
return true;
}
};
int main() {
string s = "madam";
Solution obj;
cout << (obj.isPalindrome(s) ? "true" : "false");
return 0;
}

  • Time Complexity:
    The algorithm uses two pointers, one starting from the beginning of the string and the other from the end. In each iteration, the characters at these positions are compared, and both pointers move toward the center. Since each character is processed at most once, the total number of operations is proportional to the length of the string. Therefore, the time complexity is O(N), where N is the length of the string.

  • Space Complexity:
    The algorithm only uses a constant amount of extra memory in the form of two pointer variables (left and right). No additional data structures, arrays, or strings are created during execution. Therefore, the space complexity is O(1).

FAQs about Check if String is Palindrome

1. What is a palindrome string?
A string that remains the same after reversing is called a palindrome.

2. Is "madam" a palindrome?
Yes, because reversing "madam" gives "madam".

3. Is "hello" a palindrome?
No, because reversing "hello" gives "olleh".

4. What is the best approach to check a palindrome string?
The two-pointer approach is better because it checks the string in-place.

5. Why is the two-pointer approach better?
It avoids creating an extra reversed string and uses constant space.

6. Does uppercase and lowercase matter?
Yes. "Madam" and "madam" are different unless case is ignored.










String

Read Similar Blogs

TrieArraysData StructuresHashingStringSorting

Design Add and Search Words Data Structure

Design a data structure that supports adding words and searching words later. The search word may contain lowercase letters and the dot character . . The dot . can match any one lower...

50.7k
StringRecursionArrays

Introduction to String Advanced

1. Basic Pattern Matching Problem Suppose a word needs to be searched inside a larger sentence or string. The goal is to find all starting positions where the smaller pattern exactly...

66.8k
String

Introduction to Prefix-Suffix in String

Given a string s , find the length of the longest proper prefix that is also a suffix. A proper prefix means the whole string itself is not allowed. So if s = "aaaa" , the answer is 3...

81.6k
Comments0