Check If The String Is A Palindrome

Easy
0/40
Average time to solve is 10m
profile
Contributed by
472 upvotes
Asked in companies
GrabIntuitTech Mahindra

Problem statement

You are given a string 'S'. Your task is to check whether the string is palindrome or not. For checking palindrome, consider alphabets and numbers only and ignore the symbols and whitespaces.

Note :

String 'S' is NOT case sensitive.

Example :

Let S = “c1 O$d@eeD o1c”.
If we ignore the special characters, whitespaces and convert all uppercase letters to lowercase, we get S = “c1odeedo1c”, which is a palindrome. Hence, the given string is also a palindrome.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The very first line of input contains an integer 'T' denoting the number of test cases. 

The first line of every test case contains the string 'S'.
Output format : 
For each test case, print “Yes” if 'S' is a palindrome, and “No” otherwise.

Print the output of each test case in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up : 
Can you solve the problem using O(1) space complexity?
Constraints : 
1 <= T <= 100 
1 <= Length(S) <= 10^4

Where 'T' denotes the number of test cases and 'S' denotes the given string.

Time Limit : 1 sec
Sample Input 1 :
2
N2 i&nJA?a& jnI2n
A1b22Ba
Sample Output 1 :
Yes
No
Explanation 1 :
For the first test case, S = “N2 i&nJA?a& jnI2n”. If we ignore the special characters, whitespaces and convert all uppercase letters to lowercase, we get S = “n2injaajni2n”, which is a palindrome. Hence, the given string is also a palindrome.

For the second test case, S = “A1b22Ba”. If we ignore the special characters, whitespaces and convert all uppercase letters to lowercase, we get S = “a1b22ba”, which is not a palindrome. Hence, the given string is not a palindrome.
Sample Input 2 :
3
codingninjassajNiNgNidoc
5?36@6?35
aaBBa@
Sample Output 2 :
Yes
Yes
No
Hint

A simple and intuitive approach could be to compare the given string with its reversed form and check whether they are equal or not. Ignoring the symbols, whitespaces and case during the comparison.

Approaches (2)
Reverse and Compare
  • A palindrome string is a sequence of characters which reads the same backward as forward. We use this property of palindrome to check whether the given string is a palindrome or not.
  • First off, we convert the given string to lowercase, this would make it easier for us to check for palindrome.
  • Now, the idea is to reverse the given string and store it in another variable.
  • We need to compare the original string with the reversed one.
  • During the comparison, we ignore the special characters, whitespaces and case of the string and consider only the alphabets and numbers.
  • We keep two pointers i and j, pointing to start of the given string and the reversed string respectively.
  • During each iteration, if both the pointer point to valid characters (i.e. alphabets or numbers only), we check if both the characters are equal or not.
    • If both characters are equal, we increment ith pointer and the jth pointer.
    • Otherwise, the string is not a palindrome.
  • Otherwise, if a pointer doesn’t point to a valid character (symbols and whitespaces are not valid), we skip that character and move the pointer to the next index.
  • We stop the iteration when the pointers reach the end of the string.
  • In this way, we can check if the given string is a palindrome or not.
Time Complexity

O(Length(S)), where S is the given string.

 

In the worst case, reversing and comparing the string S requires O(Length(S)) operations. Hence, the overall time complexity is O(Length(S)).

Space Complexity

O(Length(S)), where S is the given string.

 

In the worst case, extra space O(Length(S)) is required to store the reversed string. Hence, the overall space complexity is O(Length(S)).

Code Solution
(100% EXP penalty)
Check If The String Is A Palindrome
Full screen
Console