Valid Palindrome with One Character Removal

Given a string s, determine whether it can be transformed into a palindrome by removing at most one character. A palindrome is a string that reads the same backward as forward.

If the string is already a palindrome, it is considered valid. The solution should run in linear time complexity.

For example, the string "abca" can become a palindrome by removing the character 'c' (or alternatively the first 'a'), thus it is valid, whereas the string "abcdef" cannot be converted into a palindrome by removing just one character.

inputFormat

Input is provided via stdin as a single line containing the string s. The string s may be empty and can include spaces and other printable characters.

outputFormat

Output to stdout a single line: 'True' if the string can be converted into a palindrome by removing at most one character, otherwise 'False'.## sample

racecar

True