String palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters.

Palindrome

A palindrome is a word, number, phrase, or other sequences of characters which read the same backwards and forwards.

Example:

If the input string happens to be, "malayalam" then as we see that this word can be read the same as forward and backwards, it is said to be a valid palindrome. The expected output for this example will print, 'true'.

From that being said, you are required to return a boolean value from the function that has been asked to implement.

Input Format:

The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case.

Output Format:

The only line of output prints either 'true' or 'false'.

Note:

You are not required to print anything. It has already been taken care of.

Constraints:

0

Question

String palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters.

Palindrome

A palindrome is a word, number, phrase, or other sequences of characters which read the same backwards and forwards.

Example:

If the input string happens to be, "malayalam" then as we see that this word can be read the same as forward and backwards, it is said to be a valid palindrome.

The expected output for this example will print, 'true'.

From that being said, you are required to return a boolean value from the function that has been asked to implement.

Input Format:

The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case.

Output Format:

The only line of output prints either 'true' or 'false'.

Note:

You are not required to print anything. It has already been taken care of.

Constraints:

0 <= N <= 10^6
Where N is the length of the input string.

Time Limit: 1 second

Accepted Answer

Space Complexity: Explanation: Time Complexity: Explanation:

Accepted Answer

We could use 2 indices (i to go from 0->n and j to go from n->0) and continously check if the character at the index i is equal to character at index j, if it is not the case, simply return false, no need to check further (as we have already found an index where the character at i isn't the same as character at j). If the string is a palindrome, we can return true at the end of the function.

Here is C++ program for the same.

#include 

using namespace std;

bool isPal(string s)
{
    int i = 0, j = s.size() - 1;
    
    while(i < j)
    {
        if(s[i] != s[j])
        {
            return false;
        }
        
        i++;
        j--;
    }
    
    return true;
}

int main()
{
    string s;
    cin>>s;
    
    if(isPal(s))
    {
        cout<<"true";
    }
    
    else
    {
        cout<<"false";
    }
    
    return 0;
}

Output of above code is:

for input "malayalam":

malayalam
true

for input "book":

book
false

for input "noon":

noon
true

Time Complexity: O(n).