Is it a palindrome

Easy

2000 ms limit256 MB memoryTwo pointers Strings

Stuck?

Show a hint

Put one index at each end. Skip anything that is not a letter or digit, compare the rest in lowercase, and move both inward.

The ideas behind this problem

Functions, helpers and what happens to arguments Two pointers: replacing a nested loop with a single pass Input, output and strings Functions and pointers to variables Strings Functions and references Strings and StringBuilder Methods Strings, formatting and input Functions

Next in this lesson

Reads the same backwards

A palindrome reads the same forwards and backwards. Ignore anything that is not a letter or a digit, and treat capitals as the same as lowercase.

Worked example#

For Was.it.a.car.or.a.cat.I.saw, strip out the punctuation and lower the case to get wasitacaroracatisaw. Now put one finger at each end and walk them toward each other:

left	right	same?
w	w	yes
a	a	yes
s	s	yes
i	i	yes
...	...	yes

The fingers meet without ever disagreeing, so it is a palindrome.

For raceacar the first comparison is r against r, then a against a, then c against c, then e against a, which differ. Not a palindrome.

You could reverse the string and compare, which is clear and costs a second copy. Two fingers walking inward cost nothing extra and stop at the first disagreement.

Constraints#

1 <= length <= 200000
The text is a single run with no spaces. It may contain letters, digits and punctuation

Input

s is one run of text with no spaces. It may contain punctuation.

Output

true or false.

Examples

Input

amanaplanacanalpanama

Output

true

Reading it backwards gives exactly the same letters.

Input

raceacar

Output

false

The fourth letter from the left is e and from the right is a, so it fails.

Input

Output

true

A single character is the same read either way.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.