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:

ABCBA

Output:

Yes

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:

ABCD

Output:

No

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

# initializing string
s = "ABCBA"

# Initializing pointers
low = 0
high = len(s)-1

flag = 0
# Checking conditions in the loop
while(low<=high):
    # If string are unequal return No            
    if(s[low]!=s[high]):
        print("No")
        flag=1
        break
    low+=1
    high-=1

# means string is palindrome   
if(flag==0):
    print("Yes")

C++ Implementation

#include <stdio.h>
#include <string.h>


int main()
{
    // initializing string
    char s[] = "ABCBA";

    //  Initializing pointers
    int low = 0;
    int high = strlen(s) - 1;
    int flag = 0;

    // Checking conditions in the loop
    while (low<=high){
        //  If string are unequal return No            
        if (s[low++] != s[high--]){
            printf("No");
            flag = 1;
            break;
        }
    }
    //  means string is palindrome   
    if(flag==0)
        printf("Yes");
    return 0;
}

Java Implementation

class Code {


    public static void main(String[] args)
    {
        // initializing string
        String str = "ABCBA";

        //  Initializing pointers
        int low = 0, high = str.length() - 1;
        int flag = 0;

        // Checking conditions in the loop
        while (low <= high) {
            //  If string are unequal return No
            if (str.charAt(low) != str.charAt(high)){
                System.out.print("No");
                flag = 1;
                break;
            }
            low++;
            high--;
        }
        //  means string is palindrome   
        if(flag==0)
            System.out.print("Yes");
    }
}

Output:

Yes

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

def isPallindrome(s):
    # Initializing pointers
    low = 0
    high = len(s)-1

    # Checking conditions in the loop
    while(low<=high):

        if(s[low]!=s[high]):
            # If string are unequal return No            
            return "No"
        low+=1
        high-=1
    # means string is palindrome    
    return "Yes"

# initializing string
s = "ABCBA"
print(isPallindrome(s))

C++ implementation

#include <stdio.h>
#include <string.h>

void isPalindrome(char s[])
{
    //  Initializing pointers
    int low = 0;
    int high = strlen(s) - 1;

    //  Checking conditions in the loop
    while (low<=high)
    {
        if (s[low++] != s[high--])
        {
            // If string are unequal return No            
            printf("No");
            return;
        }
    }
    // means string is palindrome    
    printf("Yes");
}

int main()
{
    //  initializing string
    isPalindrome("abcba");
    return 0;
}

Java implementation

class Code {

    static String isPalindrome(String str)
    {
        //  Initializing pointers
        int low = 0, high = str.length() - 1;

        //  Checking conditions in the loop
        while (low <= high) {

            // If string are unequal return No            
            if (str.charAt(low) != str.charAt(high))
                return "No";

            low++;
            high--;
        }

        // means string is palindrome    
        return "Yes";
    }

    public static void main(String[] args)
    {
        //  initializing string
        String str = "ABCBA";

        System.out.print(isPalindrome(str));

    }
}

Output:

Yes

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

def isPalindrome(s, low, high):
    if(low==high):
        # We have reached the mid
        return True

    if(s[low]!=s[high]):
        # If unequal return false         
        return False

    if(low<=high):
        # increasing pointers and passing in recusive call         
        return isPalindrome(s, low+1, high-1)

    return True


# initializing string
s = "ABCBA"
print(isPalindrome(s, 0, len(s)-1))

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(char s[], int low, int high)
{

    // We have reached the mid
    if (low == high)
        return true;

    // If unequal return false         
    if (s[low] != s[high])
        return false;

    if (low <= high)
        // increasing pointers and passing in recusive call 
        return isPalindrome(s, low + 1, high- 1);

    return true;
}

int main()
{
    char s[] = "ABCBA";
    if(isPalindrome(s, 0, strlen(s)-1)){
        cout << "True";
    }
    else{
        cout << "False";
    }

    return 0;
}

Java Implementation

class Code {

    static boolean isPalindrome(String str, int low, int high){
        // We have reached the mid
        if (low == high)
            return true;

        // If unequal return false         
        if ((str.charAt(low)) != (str.charAt(high)))
            return false;

        if (low <= high)
            // increasing pointers and passing in recusive call         
            return isPalindrome(str, low + 1, high - 1);

        return true;
    }

    public static void main(String[] args)
    {
        String str = "ABCBA";
        if(isPalindrome(str, 0, str.length()-1)){
            System.out.print("True");    
        }
        else{
            System.out.print("False");
        }
    }
}

Output:

True

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

def isPallindrome(s):
    # Reversing the string
    rev = s[::-1]

    # checking for palindrome
    if(s==rev):
        return "Yes"
    else:
        return "No"

# initializing string
s = "ABCBA"
# Printing the ans
print(isPallindrome(s))

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

void isPalindrome(string s)
{

    string rev = s;

    //  Reversing the string 
    reverse(rev.begin(), rev.end());

    // checking for palindrome 
    if(s==rev){
        printf("Yes");
    }
    else{
        printf("No");
    }

}

int main()
{
    // initializing and passing the string
    isPalindrome("abcba");
    return 0;
}

Java Implementation

import java.lang.*;
import java.io.*;
import java.util.*;

class Code {
    static void isPalindrome(String str){
        StringBuilder rev = new StringBuilder();

        rev.append(str);

        //  Reversing the string 
        rev.reverse();

        // checking for palindrome 
        if(str.equals(rev.toString())){
            System.out.print("Yes");    
        }
        else{
            System.out.print("No");
        }
    }

    public static void main(String[] args){
        // initializing and passing the string 
        String str = "ABCBA";
        isPalindrome(str);
    }
}

Output:

Yes

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.

Conclusion

• A string is called as a palindrome string if the reverse of the given string is same as the original string.
• There are differen approaches to check for a palindrome string like using recursion, string library or standard method.