Check If The String Is A Palindrome
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.

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

Question

Check If The String Is A Palindrome

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.

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

Accepted Answer

Approach 1 :
1) Initialise a string named rev with the given string .
2) Reverse the string rev.
3) Now, if s is a palindrome then we would have rev==s , return true if rev==s and false otherwise

TC : O(N) where N=length of the string
SC : O(1)

Approach 2(Using Two Pointers) :
1) Keep pointer i=0 and j=n-1 where n=length of the string
2) Run a loop till i<=j and check if s[i]==s[j] for the condition of palindrome
3) If at any point s[i]!=s[j] then simply return false from the loop
4) Else return true after the end of the loop.

TC : O(N)
SC : O(1)

Accepted Answer

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.

Space Complexity: OtherExplanation:

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)).

Time Complexity: OtherExplanation:

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)).

Accepted Answer

Iterate from Start and End

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 whole string to lowercase, this would make it easier for us to check for palindrome.
Now, the idea is to simultaneously iterate over the start and end of the string and check if the string is a palindrome.
During the iteration, 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 and end of the string respectively.
The ith pointer traverses the string from the start, whereas the jth pointer traverses the string from the end.
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 the ith pointer and decrement 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 both the pointers become equal, i.e. i=j.
In this way, we can check if the given string is palindrome or not.

Space Complexity: O(1)Explanation:

O(1).

Constant space is being used. Hence, the overall space complexity is O(1).

Time Complexity: OtherExplanation:

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

In the worst case, we iterate over the complete string S that takes O(Length(S)) time. Hence, the overall time complexity is O(Length(S)).

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 :

Example :

Input format :

Output format :

Note :

Follow Up :

Constraints :

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer