Efficient Palindrome Check in Python (O(1) Space) – Real Python

Given a string str. The string may contain lowercase letters, special characters, numbers or even spaces. The task is to check if only the letters present in the string form a palindrome combination, without using any extra spaces.

Note: No extra space is allowed to resolve this issue. In addition, the letters present in the string are all lowercase, and the string may contain special characters, numbers and even spaces, as well as lowercase letters.

Example:

Input : str = “m a 343 la y a l am”
Output : YES
The characters in the string form the sequence “malayalam”, which is a palindrome.
Input : str = “malayalam”
Output : YES

Method:

Create two utility functions to get the first and last positions of the characters that appear in the string.
Start iterating through the string, each time always looking for the position of the first and last character.
If the first and last characters of each iteration are the same, and the string is fully traversed, then “Yes” is printed, otherwise “No” is printed.

Here’s an implementation of the above method:

Table of Contents

C ++

// CPP program to check if the characters in
// the given string forms a Palindrome in
// O(1) extra space
#include <iostream>
using namespace std;
  
// Utilty function to get the position of
// first character in the string
int firstPos(string str, int start, int end)
{
     int firstChar = -1;
  
     // Get the position of first character
     // in the string
     for ( int i = start; i <= end; i++) {
         if (str[i] >= 'a' && str[i] <= 'z' ) {
             firstChar = i;
             break ;
         }
     }
  
     return firstChar;
}
  
// Utilty function to get the position of
// last character in the string
int lastPos(string str, int start, int end)
{
     int lastChar = -1;
  
     // Get the position of last character
     // in the string
     for ( int i = start; i >= end; i--) {
         if (str[i] >= 'a' && str[i] <= 'z' ) {
             lastChar = i;
             break ;
         }
     }
  
     return lastChar;
}
  
// Function to check if the characters in
// the given string forms a Palindrome in
// O(1) extra space
bool isPalindrome(string str)
{
     int firstChar = 0, lastChar = str.length() - 1;
     bool ch = true ;
  
     for ( int i = 0; i < str.length(); i++) {
         firstChar = firstPos(str, firstChar, lastChar);
         lastChar = lastPos(str, lastChar, firstChar);
  
         // break, when all letters are checked
         if (lastChar < 0 || firstChar < 0)
             break ;
         if (str[firstChar] == str[lastChar]) {
             firstChar++;
             lastChar--;
             continue ;
         }
  
         // if mismatch found, break the loop
         ch = false ;
         break ;
     }
  
     return (ch);
}
  
// Driver code
int main()
{
     string str = "m     a  343 la y a l am" ;
     if (isPalindrome(str))
         cout << "YES" ;
     else
         cout << "NO" ;
  
     return 0;
}

Java

// Java program to check if 
// the characters in the given
// string forms a Palindrome 
// in O(1) extra space
import java.io.*;
  
class GFG 
{
  
// Utilty function to get 
// the position of first
// character in the string
static int firstPos(String str, int start, int end)
{
     int firstChar = - 1 ;
      
     // Get the position of 
     // first character in
     // the string
     for ( int i = start; i <= end; i++)
     {
         if (str.charAt(i) >= 'a' && 
         str.charAt(i) <= 'z' )
         {
             firstChar = i;
             break ;
         }
     }
      
     return firstChar;
}
  
// Utilty function to get 
// the position of last 
// character in the string
static int lastPos(String str, int start, int end)
{
     int lastChar = - 1 ;
      
     // Get the position of last 
     // character in the string
     for ( int i = start; i >= end; i--)
     {
         if (str.charAt(i) >= 'a' && 
         str.charAt(i) <= 'z' )
         {
             lastChar = i;
             break ;
         }
     }
      
     return lastChar;
}
  
// Function to check if the 
// characters in the given 
// string forms a Palindrome 
// in O(1) extra space
static boolean isPalindrome(String str)
{
     int firstChar = 0 , lastChar = str.length() - 1 ;
     boolean ch = true ;
  
     for ( int i = 0 ; i < str.length(); i++) 
     {
         firstChar = firstPos(str, firstChar, lastChar);
         lastChar = lastPos(str, lastChar, firstChar);
  
         // break, when all 
         // letters are checked
         if (lastChar < 0 || firstChar < 0 )
             break ;
         if (str.charAt(firstChar) == 
             str.charAt(lastChar)) 
         {
             firstChar++;
             lastChar--;
             continue ;
         }
          
         // if mismatch found, // break the loop
         ch = false ;
         break ;
     }
  
         return ch;
  
}
  
// Driver code
public static void main (String[] args) 
{
     String str = "m a 343 la y a l am" ;
      
     if (isPalindrome(str))
         System.out.print( "YES" );
     else
     System.out.println( "NO" );
}
}
  
// This code is contributed 
// by inder_verma.

Python 3

# Python 3 program to check if the characters 
# in the given string forms a Palindrome in
# O(1) extra space
  
# Utilty function to get the position of
# first character in the string
def firstPos( str , start, end):
  
     firstChar = - 1
  
     # Get the position of first character
     # in the string
     for i in range (start, end + 1 ):
         if ( str [i] > = 'a' and str [i] < = 'z' ) :
             firstChar = i
             break
  
     return firstChar
  
# Utilty function to get the position of
# last character in the string
def lastPos( str , start, end):
  
     lastChar = - 1
  
     # Get the position of last character
     # in the string
     for i in range (start, end - 1 , - 1 ) :
         if ( str [i] > = 'a' and str [i] < = 'z' ) :
             lastChar = i
             break
  
     return lastChar
  
# Function to check if the characters in
# the given string forms a Palindrome in
# O(1) extra space
def isPalindrome( str ):
  
     firstChar = 0
     lastChar = len ( str ) - 1
     ch = True
  
     for i in range ( len ( str )) :
         firstChar = firstPos( str , firstChar, lastChar);
         lastChar = lastPos( str , lastChar, firstChar);
  
         # break, when all letters are checked
         if (lastChar < 0 or firstChar < 0 ):
             break
         if ( str [firstChar] = = str [lastChar]):
             firstChar + = 1
             lastChar - = 1
             continue
  
         # if mismatch found, break the loop
         ch = False
         break
  
     return (ch)
  
# Driver code
if __name__ = = "__main__" :
      
     str = "m     a 343 la y a l am"
     if (isPalindrome( str )):
         print ( "YES" )
     else :
         print ( "NO" )
  
# This code is contributed by ita_c

C#

// C# program to check if 
// the characters in the given
// string forms a Palindrome 
// in O(1) extra space
using System;
  
class GFG 
{
  
// Utilty function to get 
// the position of first
// character in the string
static int firstPos( string str, int start, int end)
{
     int firstChar = -1;
      
     // Get the position of 
     // first character in
     // the string
     for ( int i = start; i <= end; i++)
     {
         if (str[i] >= 'a' && 
            str[i] <= 'z' )
         {
             firstChar = i;
             break ;
         }
     }
      
     return firstChar;
}
  
// Utilty function to get 
// the position of last 
// character in the string
static int lastPos( string str, int start, int end)
{
     int lastChar = -1;
      
     // Get the position of last 
     // character in the string
     for ( int i = start; i >= end; i--)
     {
         if (str[i] >= 'a' && 
            str[i] <= 'z' )
         {
             lastChar = i;
             break ;
         }
     }
      
     return lastChar;
}
  
// Function to check if the 
// characters in the given 
// string forms a Palindrome 
// in O(1) extra space
static bool isPalindrome( string str)
{
     int firstChar = 0, lastChar = str.Length - 1;
     bool ch = true ;
  
     for ( int i = 0; i < str.Length; i++) 
     {
         firstChar = firstPos(str, firstChar, lastChar);
         lastChar = lastPos(str, lastChar, firstChar);
  
         // break, when all 
         // letters are checked
         if (lastChar < 0 || firstChar < 0)
             break ;
         if (str[firstChar] == 
             str[lastChar]) 
         {
             firstChar++;
             lastChar--;
             continue ;
         }
          
         // if mismatch found, // break the loop
         ch = false ;
         break ;
     }
  
         return ch;
}
  
// Driver code
public static void Main () 
{
     string str = "m a 343 la y a l am" ;
      
     if (isPalindrome(str))
         Console.WriteLine( "YES" );
     else
         Console.WriteLine( "NO" );
}
}
  
// This code is contributed 
// by inder_verma.

PHP

<?php
// PHP program to check if the 
// characters in the given 
// string forms a Palindrome 
// in O(1) extra space
  
// Utilty function to get the 
// position of first character
// in the string
function firstPos( $str , $start , $end )
{
     $firstChar = -1;
  
     // Get the position of first 
     // character in the string
     for ( $i = $start ; $i <= $end ; $i ++) 
     {
         if ( $str [ $i ] >= 'a' and
             $str [ $i ] <= 'z' ) 
         {
             $firstChar = $i ;
             break ;
         }
     }
  
     return $firstChar ;
}
  
// Utilty function to get the 
// position of last character
// in the string
function lastPos( $str , $start , $end )
{
     $lastChar = -1;
  
     // Get the position of last 
     // character in the string
     for ( $i = $start ; $i >= $end ; $i --) 
     {
         if ( $str [ $i ] >= 'a' and 
             $str [ $i ] <= 'z' ) 
         {
             $lastChar = $i ;
             break ;
         }
     }
  
     return $lastChar ;
}
  
// Function to check if the 
// characters in the given 
// string forms a Palindrome 
// in O(1) extra space
function isPalindrome( $str )
{
     $firstChar = 0; 
     $lastChar = count ( $str ) - 1;
     $ch = true;
  
     for ( $i = 0; $i < count ( $str ); $i ++) 
     {
         $firstChar = firstPos( $str , $firstChar , $lastChar );
         $lastChar = lastPos( $str , $lastChar , $firstChar );
  
         // break, when all letters are checked
         if ( $lastChar < 0 or $firstChar < 0)
             break ;
         if ( $str [ $firstChar ] == $str [ $lastChar ])
         {
             $firstChar ++;
             $lastChar --;
             continue ;
         }
  
         // if mismatch found, // break the loop
         $ch = false;
         break ;
     }
  
     return ( $ch );
}
  
// Driver code
$str = "m a 343 la y a l am" ;
if (isPalindrome( $str ))
     echo "YES" ;
else
     echo "NO" ;
  
// This code is contributed 
// by inder_verma.
?>

The output is as follows:

YES

Data Structures and Algorithms, IT Technology

Efficient Palindrome Check in Python (O(1) Space) – Real Python

C ++

Java

Python 3

C#

PHP

Thao Nguyen