Palindrome String

A Palindrome string is a string which is equal to its reverse or we can say a string is palindrome if the reverse of the string is the same as the original one.

Properties of Palindrome String

A palindrome string is characterized by its symmetric structure, where the characters in the first half mirror those in the second half in reverse order. Additionally, any string of length 1 is inherently a palindrome.

How to identify a Palindrome?

To optimize the palindrome identification process, we can simplify the comparison by focusing on only half of the string. Here's a revised version of the steps:

• Convert the string to lowercase or uppercase, depending on the case sensitivity requirement.
• Define two pointers, one starting from the beginning of the string and the other from the end.
• Iterate through the string until the pointers meet or cross each other.
• At each step, compare the characters pointed to by the two pointers.
• If they don't match, the string is not a palindrome; otherwise, continue until all pairs are checked.
• If all pairs match, the string is a palindrome.

Problem Statement

Given a string s, we have to check whether the given string is palindrome or not.

A string is called as a palindrome string if the reverse of the given string is same as the original string.

Example

Input:

Output:

Explanation: If we reverse the given string, it will be ABCBA which is equal to the original string. Hence, it is a palindrome string.

Input:

Output:

Explanation: If we reverse the given string, it will be DCBA which is not equal to the original string. Hence, it is not a palindrome string.

Constraints

$1 <= length of string <= 2 * 10^5$

Approach 1 - Using the Standard Method

In this approach, we will be following the below algorithm:

• Make two indexes low and high respectively.
• Initialize a flag variable as 0.
• while low is not equal to high, check if s[low] is equal to s[high].
  • If s[low] is not equal to s[high], print "no" and make flag as 1.
  • In each iteration, increment the low index by 1 and decrease the high index by 1.
• After the loop execution, check if the flag value is 0 or not, If its 0 that means that the string is palindrome and print "Yes".

Python Implementation

C++ Implementation

Java Implementation

Output:

Complexity Analysis

Time Complexity: O(N) => As a single traversal is required, time complexity is O(N). Space Complexity: O(1) => No extra space is required in this operation.

Approach 2 - Using a Function

In this approach, we will be following the exactly same approach as the above one, the difference is just that we are putting the execution code in a separate function and then calling that function wherever we need.

Python Implementation

C++ implementation

Java implementation

Output:

Complexity Analysis

Time Complexity: O(N) => As a single traversal is required, time complexity is O(N). Space Complexity: O(1) => No extra space is required in this operation.

Approach 3 - Using Recursion

In this approach, we are checking the string using recursion by following the below algorithm:

• Pass the string in the recursive function along with low and high pointers. Initial values of low and high are 0 and n-1 where n is the length of the string to be checked.
• In the function, we need to check the characters at index pointed by low and high are equal or not.
• In the recursive calls, pass the string by increasing the low index value by 1 and decreasing the high index value by 1.

Python Implementation

C++ Implementation

Java Implementation

Output:

Complexity Analysis

Time Complexity: O(N) => As N/2 calls recursive calls are made, the time complexity is O(N). Space Complexity: O(1) => No extra space is required in this operation.

Approach 4 - Using String Library Functions

In this approach, we will be using a library function for reversing and then comparing a string with the reversed one: If both the strings are equal then print Yes, else No.

Python Implementation

C++ Implementation

Java Implementation

Output:

Complexity Analysis

Time Complexity: O(N) => N time is required to reverse the string and N to compare the strings, so the overall time complexity is O(N). Space Complexity: O(N) => O(N) space is required, as a new string of length to store the copy of the string.