Palindrome String

Last Updated : 21 Sep, 2024

Given a string s, the task is to check if it is palindrome or not.

Example:

Input: s = “abba”
Output: 1
Explanation: s is a palindrome

Input: s = “abc”
Output: 0
Explanation: s is not a palindrome

Using Two-Pointers – O(n) time and O(1) space

The idea is to keep two pointers, one at the beginning (left) and the other at the end (right) of the string.

Then compare the characters at these positions. If they don’t match, the string is not a palindrome, and return 0.
If they match, the pointers move towards each other (left pointer moves right, right pointer moves left) and continue checking.
If the pointers cross each other without finding a mismatch, the string is confirmed to be a palindrome, and returns 1.

Working:

C++

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

// Function to check if a string is a palindrome
int isPalindrome(string & s){

    // Initialize two pointers: one at the beginning (left)
    // and one at the end (right)
    int left = 0;
    int right = s.length() - 1;

    // Continue looping while the two pointers
    //  have not crossed each other
    while (left < right)
    {

        // If the characters at the current positions are not equal,
        // return 0 (not a palindrome)
        if (s[left] != s[right])
            return 0;

        // Move the left pointer to the right
        // and the right pointer to the left
        left++;
        right--;
    }

    // If no mismatch is found,
    // return 1 (the string is a palindrome)
    return 1;
}

int main(){
    string s = "abba";
    cout << isPalindrome(s) << endl;

    return 0;
}

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

// Function to check if a string is a palindrome
int isPalindrome(char s[]){
    int left = 0;
    int right = strlen(s) - 1;

    // Continue looping while the two pointers have not crossed
    while (left < right) {
      
        // If the characters at the current positions
        // are not equal
        if (s[left] != s[right])
            return 0;

        // Move the left pointer to the right and
        // the right pointer to the left
        left++;
        right--;
    }

    // If no mismatch is found, return 1 (palindrome)
    return 1;
}

int main(){
    char s[] = "abba";
    printf("%d\n", isPalindrome(s));
    return 0;
}

Java

class GfG{
  
    // Function to check if a string is a palindrome
    public static int isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        // Continue looping while the two pointers
        // have not crossed
        while (left < right) {
          
            // If the characters at the current positions
            // are not equal
            if (s.charAt(left) != s.charAt(right))
                return 0;

            // Move the left pointer to the right and
            // the right pointer to the left
            left++;
            right--;
        }

        // If no mismatch is found, return 1 (palindrome)
        return 1;
    }

  public static void main(String[] args) {
        String s = "abba";
        System.out.println(isPalindrome(s));
    }
}

Python

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    # Continue looping while the two pointers
    # have not crossed
    while left < right:
      
        # If the characters at the current positions
        # are not equal
        if s[left] != s[right]:
            return 0

        # Move the left pointer to the right and
        # the right pointer to the left
        left += 1
        right -= 1

    # If no mismatch is found, return 1 (palindrome)
    return 1

# Driver code
s = "abba"
print(is_palindrome(s))

using System;

class GfG {
  
    // Function to check if a string is a palindrome
    static int IsPalindrome(string s) {
        int left = 0;
        int right = s.Length - 1;

        // Continue looping while the two pointers
        // have not crossed
        while (left < right) {
          
            // If the characters at the current positions
            // are not equal
            if (s[left] != s[right])
                return 0;

            // Move the left pointer to the right and
            // the right pointer to the left
            left++;
            right--;
        }

        // If no mismatch is found, return 1 (palindrome)
        return 1;
    }

    static void Main() {
        string s = "abba";
        Console.WriteLine(IsPalindrome(s));
    }
}

JavaScript

function isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;

    // Continue looping while the two pointers
    // have not crossed
    while (left < right) {
    
        // If the characters at the current positions
        // are not equal
        if (s[left] !== s[right]) {
            return 0;
        }

        // Move the left pointer to the right and
        // the right pointer to the left
        left++;
        right--;
    }

    // If no mismatch is found, return 1 (palindrome)
    return 1;
}

// Driver code
const s = "abba";
console.log(isPalindrome(s));

Output

Time Complexity: O(n), where n is the length of the input string.
Auxiliary Space: O(1), no extra data structures used.

Optimization of two pointers approach – O(n) time and O(1) space

This approach is just an optimization of two variables that we have used in the above approach. Here, we can do the same with the help of single variable only. The idea is that:

Iterates through the first half of the string.
For each character at index i, checks if s[i] and s[length – i – 1])
- If any pair of characters don’t match, then returns 0.
If all characters match, then returns 1 (indicating the string is a palindrome).

C++

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

// Function to check if a string is a palindrome.
int isPalindrome(string &s){
  
  int len = s.length();

    // Iterate over the first half of the string
    for (int i = 0; i < len / 2; i++){

        // If the characters at symmetric positions are not equal
        if (s[i] != s[len - i - 1])

            // Return 0 (not a palindrome)
            return 0;
    }

    // If all symmetric characters are equal
    // then it is palindrome
    return 1;
}

int main(){
    string s = "abba";
    cout << isPalindrome(s) << endl;

    return 0;
}

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

// Function to check if a string is a palindrome
int isPalindrome(char s[]) {
    int len = strlen(s);

    // Iterate over the first half of the string
    for (int i = 0; i < len / 2; i++) {
      
        // If the characters at symmetric positions are not equal
        if (s[i] != s[len - i - 1])
          
            // Return 0 (not a palindrome)
            return 0;
    }

    // If all symmetric characters are equal
    // then it is palindrome
    return 1;
}

int main() {
    char s[] = "abba";
    printf("%d\n", isPalindrome(s));
    return 0;
}

Java

class GfG {

    // Function to check if a string is a palindrome
    public static int isPalindrome(String s){
        int len = s.length();

        // Iterate over the first half of the string
        for (int i = 0; i < len / 2; i++) {

            // If the characters at symmetric positions are
            // not equal
            if (s.charAt(i) != s.charAt(len - i - 1))
              
                // Return 0 (not a palindrome)
                return 0;
        }

        // If all symmetric characters are equal
        // then it is palindrome
        return 1;
    }

    public static void main(String[] args){
        String s = "abba";
        System.out.println(isPalindrome(s));
    }
}

Python

def is_palindrome(s):
    length = len(s)

    # Iterate over the first half of the string
    for i in range(length // 2):
      
        # If the characters at symmetric positions are not equal
        if s[i] != s[length - i - 1]:
          
            # Return 0 (not a palindrome)
            return 0

    # If all symmetric characters are equal
    # then it is palindrome
    return 1

# Driver code  
s = "abba"
print(is_palindrome(s))

using System;

class GfG {

    // Function to check if a string is a palindrome
    static int IsPalindrome(string s){
        int len = s.Length;

        // Iterate over the first half of the string
        for (int i = 0; i < len / 2; i++) {

            // If the characters at symmetric positions are
            // not equal
            if (s[i] != s[len - i - 1])
              
                // Return 0 (not a palindrome)
                return 0;
        }

        // If all symmetric characters are equal
        // then it is palindrome
        return 1;
    }

    static void Main(){
        string s = "abba";
        Console.WriteLine(IsPalindrome(s));
    }
}

JavaScript

// Function to check if a string is a palindrome.
function isPalindrome(s) {
    let len = s.length;

    // Iterate over the first half of the string
    for (let i = 0; i < len / 2; i++) {

        // If the characters at symmetric
        // positions are not equal
        if (s[i] !== s[len - i - 1]) {

            // Return false (not a palindrome)
            return false;
        }
    }

    // If all symmetric characters are equal
    // then it is palindrome
    return true;
}

// Driver code
let s = "abba";
console.log(isPalindrome(s));

Output

Time Complexity: O(n), where n is the length of the input string.
Auxiliary Space: O(1), no extra data structures used.

Using Recursion – O(n) time and O(n) space

This approach is similar to our two pointers approach that we have discussed above. Here, we can use recursion to check the first and last letters of a string and then recursively check for remaining part of the string.

Base case: if the length of the string is 1 or less, it’s considered a palindrome.
If the first and last characters don’t match, it’s not a palindrome, return 0.
Otherwise, recursively calls itself by incrementing left by 1 and decrementing right by 1

C++

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

// Recursive util function to check if a string is a palindrome
int isPalindromeUtil(string & s, int left, int right) {

    // Base case
    if (left >= right) 
        return 1;
    
    // If the characters at the current positions are not equal,
    // it is not a palindrome
    if (s[left] != s[right]) 
        return 0;

    // Move left pointer to the right
    // and right pointer to the left
    return isPalindromeUtil(s, left + 1, right - 1);
}

// Function to check if a string is a palindrome
int isPalindrome(string s){
    int left = 0, right = s.length() - 1;
    return isPalindromeUtil(s, left, right);
}

int main() {
    string s = "abba";
    cout << isPalindrome(s) << endl;

    return 0;
}

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

// Recursive util function to check if a string is a palindrome
int isPalindromeUtil(char *s, int left, int right){

    // Base casee
    if (left >= right)
        return 1;

    // If the characters at the current positions are not equal,
    // it is not a palindrome
    if (s[left] != s[right])
        return 0;

    // Move left pointer to the right
    // and right pointer to the left
    return isPalindromeUtil(s, left + 1, right - 1);
}

// Function to check if a string is a palindrome
int isPalindrome(char *s){
    int left = 0;
    int right = strlen(s) - 1;
    return isPalindromeUtil(s, left, right);
}

int main(){
    char s[] = "abba";
    printf("%d\n", isPalindrome(s));
    return 0;
}

Java

class GfG {

    // Recursive util function to check if a string is a
    // palindrome
    static int isPalindromeUtil(String s, int left,
                                int right){

        // Base case
        if (left >= right)
            return 1;

        // If the characters at the current positions are
        // not equal, it is not a palindrome
        if (s.charAt(left) != s.charAt(right))
            return 0;

        // Move left pointer to the right
        // and right pointer to the left
        return isPalindromeUtil(s, left + 1, right - 1);
    }

    // Function to check if a string is a palindrome
    static int isPalindrome(String s){
        int left = 0;
        int right = s.length() - 1;
        return isPalindromeUtil(s, left, right);
    }

    public static void main(String[] args){
        String s = "abba";
        System.out.println(isPalindrome(s));
    }
}

Python

def is_palindrome_util(s, left, right):
  
    # Base case
    if left >= right:
        return 1

    # If the characters at the current positions are not equal,
    # it is not a palindrome
    if s[left] != s[right]:
        return 0

    # Move left pointer to the right
    # and right pointer to the left
    return is_palindrome_util(s, left + 1, right - 1)

# Function to check if a string is a palindrome
def is_palindrome(s):
    left = 0
    right = len(s) - 1
    return is_palindrome_util(s, left, right)

# Driver code
s = "abba"
print(is_palindrome(s))

using System;

class GfG {

    // Recursive util function to check if a string is a
    // palindrome
    static int IsPalindromeUtil(string s, int left,
                                        int right){

        // Base case
        if (left >= right) 
            return 1;

        // If the characters at the current positions are
        // not equal, it is not a palindrome
        if (s[left] != s[right]) 
            return 0;

        // Move left pointer to the right and right pointer
        // to the left
        return IsPalindromeUtil(s, left + 1, right - 1);
    }

    // Function to check if a string is a palindrome
    public static int IsPalindrome(string s)
    {
        int left = 0;
        int right = s.Length - 1;
        return IsPalindromeUtil(s, left, right);
    }

    public static void Main()
    {
        string s = "abba";
        Console.WriteLine(IsPalindrome(s));
    }
}

JavaScript

function isPalindromeUtil(s, left, right){

    // Base case
    if (left >= right) 
        return 1;

    // If the characters at the current positions are not
    // equal, return 0 (not a palindrome)
    if (s[left] !== s[right]) {
        return 0;
    }

    // Move left pointer to the right and right pointer to
    // the left
    return isPalindromeUtil(s, left + 1, right - 1);
}

// Function to check if a string is a palindrome
function isPalindrome(s){
    let left = 0;
    let right = s.length - 1;
    return isPalindromeUtil(s, left, right);
}

// Driver code
let s = "abba";
console.log(isPalindrome(s));

Output

Time Complexity: O(n), Each character is checked once, and there are O(n/2) recursive calls.
Auxiliary Space: O(n), due to recursive call stack

By Reversing String – O(n) time and O(n) space

According to the definition of a palindrome, a string reads the same both forwards and backwards. So, we can use this idea and compare the reversed string with the original one.

If they are the same, the string is a palindrome, and then returns 1.
If they are different, then returns 0, meaning it’s not a palindrome.

C++

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

// Function to check if a string is a palindrome
int isPalindrome(string & s){
  
    // If reverse string is equal to given string,
    // then it is palindrome.
    return s == string(s.rbegin(), s.rend()) ? 1 : 0;
}

int main(){
    string s = "abba";
    cout << isPalindrome(s) << endl;

    return 0;
}

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

// Function to check if a string is a palindrome
int isPalindrome(char s[]){
    int length = strlen(s);
    char reversed[length + 1];
    
    // Reverse the string
    for (int i = 0; i < length; i++) {
        reversed[i] = s[length - i - 1];
    }
    reversed[length] = '\0';

    // Check if the reversed string is equal to the original
    return strcmp(s, reversed) == 0 ? 1 : 0;
}

int main(){
    char s[] = "abba";
    printf("%d\n", isPalindrome(s));
    
    return 0;
}

Java

class GfG {

    // Function to check if a string is a palindrome
    static int isPalindrome(String s){

        // If reverse string is equal to given string,
        // then it is palindrome.
        return s.equals(new StringBuilder(s)
                            .reverse()
                            .toString() ? 1 : 0;
    }

    public static void main(String[] args){
        String s = "abba";
        System.out.println(isPalindrome(s));
    }
}

Python

def is_palindrome(s):
  
    #If reverse string is equal to given string,
    # then it is palindrome.
    return 1 if s == s[::-1] else 0

# Driver code
s = "abba"
print(is_palindrome(s))

using System;

class GfG{
  
    // Function to check if a string is a palindrome
    static int IsPalindrome(string s) {
      
        // If reverse string is equal to given string,
        // then it is palindrome.
        char[] charArray = s.ToCharArray();
        Array.Reverse(charArray);
        string reversed = new string(charArray);
        return s.Equals(reversed) ? 1 : 0;
    }

    static void Main() {
        string s = "abba";
        Console.WriteLine(IsPalindrome(s));
    }
}

JavaScript

function isPalindrome(s) {

    // If reverse string is equal to given string,
    // then it is palindrome.
    const reversed = s.split('').reverse().join('');
    return s === reversed ? 1 : 0;
}

// Driver code
const s = "abba";
console.log(isPalindrome(s));

Output

Time Complexity: O(n), where n is the length of the input string.
Auxiliary Space: O(n), for creating another string

Related Article:

Palindrome String Coding Problems

Palindrome Number Program in C

rokadetushar8840

Improve

Article Tags :

Practice Tags :

Palindrome String

Using Two-Pointers – O(n) time and O(1) space

Optimization of two pointers approach – O(n) time and O(1) space

Using Recursion – O(n) time and O(n) space

By Reversing String – O(n) time and O(n) space

Similar Reads

Check Palindrome by Different Language

Easy Problems on Palindrome

Medium Problems on Palindrome

Hard Problems on Palindrome

What kind of Experience do you want to share?