Posted on by Kalkicode
Code String

Display palindrome in rotated string

Normally we are check palindrome in given string. But in special case when rotated string is creating a palindrome. And our goal is to find that sequences which is contains in given string. For Example

Example 1
input : GFEFFEF 
O/p   : FEFGFEF

Example 2
input : BAACCAAB 
O/p   : CAABBAAC

Example 3:
input : ABAE 
O/p   : Not a rotational palindrome

Example 4
input : ABACCCCCCCCABA 
O/p   : CCCCABAABACCCC

Example 5
input : ABACCCCCCCCCABA 
O/p   : Not a rotational palindrome

Example 6
input : AAAAAAAACAA 
O/p   : AAAAACAAAAA

 

In this article, we will discuss a problem of finding palindromes in rotated strings. We will explore the problem statement, provide an explanation with a suitable example, present the algorithm and pseudocode, and explain the resultant output. Additionally, we will analyze the time complexity of the code.

Problem Statement:

Given a string, we need to determine if there exists a palindrome in the string after rotating it. A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. For example, "level" and "radar" are palindromes.

Example:

Let's consider the string "BAABACCCCCCCCCA" as an example. We want to check if there is a palindrome in the string after rotating it. After rotating the string, we get "ABACCCCCCCCCABA". In this case, the rotated string contains a palindrome, which is "ABACCCCCCCCCABA".

Algorithm:

1. Define a function "palindrome" that takes the string, starting index, ending index, and size as parameters.

2. Initialize a variable "status" to 1, which represents the existence of a palindrome.

3. Initialize a variable "counter" to 0 for iteration.

4. Start a loop from 0 to size-2:

a. Check if the character at the start index is equal to the character at the end index in the string.

b. If they are not equal, set "status" to 0 (indicating no palindrome) and break out of the loop.

c. Increment the start index and decrement the end index.

d. If the start index exceeds size-2, set it to 0 (to check for a rotated string).

e. If the end index is less than 0, set it to size-2 (to check for a rotated string).

5. Return the value of "status".

6. Define a function "find" that takes the string and size as parameters.

7. If the size is less than or equal to 1, return from the function.

8. Initialize variables "j" and "result" to 0.

9. Initialize a variable "status" to 0, which represents the existence of a palindrome.

10. Initialize variables "x" and "y" to 0, which store the indices of the palindrome.

11. Start a loop from 1 to size-2:

a. If the character at the current index (i) is equal to the character at index j, check for a palindrome.

b. If a palindrome is found, set "status" to 1, and store the indices "x" and "y".

c. If a palindrome is not found, update j to the current index (i).

12. If a palindrome is found:

a. Print the original string.

b. Start a loop from "x" to "y" (exclusive):

- Print the character at index "x".

- Increment "x" and wrap around if it reaches size-1.

c. Print the character at index "y" (the last element of the palindrome).

d. Print a new line character.

13. If a palindrome is not found, print that the string is not a rotational palindrome.

14. Define a function "display" that takes the string, start index, and end index as parameters.

15. Start a loop from the start index to the end index:

- Print each character of the string within the specified range.

16. In the main function:

a. Declare the input strings.

b. Get the size of each string using the sizeof function.

c. Call the "find" function for each string to check for palindromes in rotated strings.

17. Return 0 to exit the program.

Pseudocode:

function palindrome(str, start, end, size):
    status = 1
    counter = 0
    for i in range 0 to size-2:
        if str[start] != str[end]:
            status = 0
            break
        start++
        end--
        if start > size-2:
            start = 0
        if end < 0:
            end = size-2
    return status

function find(str, size):
    if size <= 1:
        return
    j = 0
    result = 0
    status = 0
    x = 0
    y = 0
    for i in range 1 to size-2:
        if str[i] == str[j]:
            status = palindrome(str, i, j, size)
        if status == 1:
            x = i
            y = j
            break
        j = i
    if status == 1:
        print str
        while x != y:
            print str[x]
            x++
            if x == size-1:
                x = 0
        print str[y]
        print newline
    else:
        print str + " : Not a rotational palindrome"

function display(str, start, end):
    for i in range start to end:
        print str[i]

function main():
    size = 0
    str1 = "BAABACCCCCCCCCA"
    size = sizeof(str1) / sizeof(str1[0])
    find(str1, size)
    str2 = "BAABCC"
    size = sizeof(str2) / sizeof(str2[0])
    find(str2, size)
    str3 = "CBAABCD"
    size = sizeof(str3) / sizeof(str3[0])
    find(str3, size)
    str4 = "BABE"
    size = sizeof(str4) / sizeof(str4[0])
    find(str4, size)
    str5 = "BAAB"
    size = sizeof(str5) / sizeof(str5[0])
    find(str5, size)
    return 0

Code Solution

Here given code implementation process.

//C Program
//Display palindrome in rotated string
#include<stdio.h>

//This function are capable to check palindrome in 
//rotated and simple string using two index
int palindrome(char *str,int start,int end,int size)
{
  int status=1;
  int counter=0;
  
  //This loop is executed in linear time
  for (int i = 0; i <= size-2 ; ++i)
  {
    if(str[start]!=str[end])
    {
      //When not exist palindrome
      status=0;
      break;
    }
    //Modify the start and end values
    start++;
    end--;

    //When needed to check rotated string
    if((start)>size-2)
    {
      //Get new start
      start=0;
    }
    if(end<0)
    {
      //Get new end
      end=size-2;
    }
  }
  
  return status;
}

void find(char *str,int size)
{
  if(size<=1) return;

  int j=0,result=0;
  int status=0;
  int x=0,y=0;

  for (int i = 1; i <=size-2;  i++)
  {
    //if i and j values are same then possible 
    //string contain palindrome
    if(str[i]==str[j])
    {
      //check palindrome
      status=palindrome(str,i,j,size);
    }
   
    if(status==1)
    {
      //when get palindrome 
      x=i;
      y=j;
      break;
    }
    //When needed to check palindrome in rotated string
    j=i;
  }

  if(status==1)
  {
     printf("%s : ",str);
    //palindrome sequence
    while(x!=y)
    {
      printf("%c",str[x] );
      x++;
      if(x==size-1)
      {
        x=0;
      }
    }
    printf("%c",str[y] );//last element
    printf("\n");
  
  }else
  {
    //When string is not a palindrome
    printf("%s : Not a rotational palindrome\n",str);
  }
}

//Display element 
void display(char *str,int start,int end)
{
  
  for (int i = start; i <= end; ++i)
  {
    printf("%c",str[i] );
  }
 
}
int main()
{
  int size=0;
 
  char str1[]="BAABACCCCCCCCCA";
  
  size=sizeof(str1)/sizeof(str1[0]);
  find(str1,size);  //ABACCCCCCCCCABA  


  char str2[]="BAABCC";

  size=sizeof(str2)/sizeof(str2[0]);
  find(str2,size);  //ABCCBA
 
  
  char str3[]="CBAABCD";

  size=sizeof(str3)/sizeof(str3[0]);
  find(str3,size);   //ABCDCBA


  char str4[]="BABE";


  size=sizeof(str4)/sizeof(str4[0]);
  find(str4,size);  //Not a Rotated palindrome



  char str5[]="BAAB";


  size=sizeof(str5)/sizeof(str5[0]);
  find(str5,size); //ABBA
 
  return 0;
}

Output

BAABACCCCCCCCCA : ABACCCCCCCCCABA
BAABCC : ABCCBA
CBAABCD : ABCDCBA
BABE : Not a rotational palindrome
BAAB : ABBA
//C++ Program 
//Display palindrome in rotated string
#include <iostream>
#include <string>
using namespace std;


class MyString
{

public:


  //This function are capable to check palindrome in 
  //rotated and simple string using two index
  int palindrome(string str,int start,int end,int size)
  {
    int status=1;
    int counter=0;

    //This loop is executed in linear time
    for (int i = 0; i < size ; ++i)
    {
      if(str[start]!=str[end])
      {
        //When not exist palindrome
        status=0;
        break;
      }
      //Modify the start and end values
      start++;
      end--;
      //When needed to check rotated string
      if((start)>size-1)
      {
      //Get new start
        start=0;
      }
      if(end<0)
      {
      //Get new end
        end=size-1;
      }
    }

    return status;
  }
  void find(string str,int size)
  {
    if(size<=1) return;
    int j=0,result=0;
    int status=0;
    int x=0,y=0;
    for (int i = 1; i <size; i++)
    {
      //if i and j values are same then possible 
      //string contain palindrome
      if(str[i]==str[j])
      {
      //check palindrome
        status=palindrome(str,i,j,size);
      }

      if(status==1)
      {
       //when get palindrome 
        x=i;
        y=j;
        break;
      }
      //When needed to check palindrome in rotated string
      j=i;
    }
    if(status==1)
    {
      cout<<str<<" : ";
      //palindrome sequence
      while(x!=y)
      {
        cout<<" "<<str[x] ;
        x++;
        if(x==size)
        {
          x=0;
        }
      }
      cout<<" "<<str[y] ;//last element
      cout<<("\n");

    }
    else
    {
      //When string is not a palindrome
      cout<<str<<" : Not a rotational palindrome\n";
    }
  }

};

int main()
{

  MyString obj;


  string str1="BAABACCCCCCCCCA";
  int size=0;
  
  size=str1.size();

  obj.find(str1,size);  //ABACCCCCCCCCABA  


  string str2="BAABCC";

  size=str2.size();
  obj.find(str2,size);  //ABCCBA

  
  string str3="CBAABCD";

  size=str3.size();
  obj.find(str3,size);   //ABCDCBA


  string str4="BABE";


  size=str4.size();;
  obj.find(str4,size);  //Not a Rotated palindrome



  string str5="BAAB";


  size=str5.size();
  obj.find(str5,size); //ABBA

  return 0;
}

Output

BAABACCCCCCCCCA :  A B A C C C C C C C C C A B A
BAABCC :  A B C C B A
CBAABCD :  A B C D C B A
BABE : Not a rotational palindrome
BAAB :  A B B A
//Java program
//Display palindrome in rotated String
public class MyString
{

  //This function are capable to check palindrome in 
  //rotated and simple String using two index
  public int palindrome(String str,int start,int end,int size)
  {
    int status=1;
    int counter=0;

    //This loop is executed in linear time
    for (int i = 0; i < size ; ++i)
    {
      if(str.charAt(start)!=str.charAt(end))
      {
        //When not exist palindrome
        status=0;
        break;
      }
      //Modify the start and end values
      start++;
      end--;
      //When needed to check rotated String
      if((start)>size-1)
      {
      //Get new start
        start=0;
      }
      if(end<0)
      {
      //Get new end
        end=size-1;
      }
    }

    return status;
  }
  public void  find(String str,int size)
  {
    if(size<=1) return;
    int j=0,result=0;
    int status=0;
    int x=0,y=0;
    for (int i = 1; i <size; i++)
    {
      //if i and j values are same then possible 
      //String contain palindrome
      if(str.charAt(i)==str.charAt(j))
      {
      //check palindrome
        status=palindrome(str,i,j,size);
      }

      if(status==1)
      {
       //when get palindrome 
        x=i;
        y=j;
        break;
      }
      //When needed to check palindrome in rotated String
      j=i;
    }
    if(status==1)
    {
      System.out.print(str+" : ");
      //palindrome sequence
      while(x!=y)
      {
        System.out.print(" "+str.charAt(x));
        x++;
        if(x==size)
        {
          x=0;
        }
      }
      System.out.print(" "+str.charAt(y) );//last element
      System.out.println();

    }
    else
    {
      //When String is not a palindrome
      System.out.println(str+" : Not a rotational palindrome\n");
    }
  }
 
  public static void main(String[] args) 
  {
    
    MyString obj = new MyString();


    String str1="BAABACCCCCCCCCA";
    int size=0;
    
    size=str1.length();

    obj.find(str1,size);  //ABACCCCCCCCCABA  


    String str2="BAABCC";

    size=str2.length();
    obj.find(str2,size);  //ABCCBA

    
    String str3="CBAABCD";

    size=str3.length();
    obj.find(str3,size);   //ABCDCBA


    String str4="BABE";


    size=str4.length();;
    obj.find(str4,size);  //Not a Rotated palindrome



    String str5="BAAB";


    size=str5.length();
    obj.find(str5,size); //ABBA


  }
}

Output

BAABACCCCCCCCCA :  A B A C C C C C C C C C A B A
BAABCC :  A B C C B A
CBAABCD :  A B C D C B A
BABE : Not a rotational palindrome

BAAB :  A B B A
#Python Program 
#Display palindrome in rotated string
class MyString:

  #This def  are capable to check palindrome in 
  #rotated and simple string using two index
  def palindrome(self,str,start,end,size) :

    status=1
    i=0
    #This loop is executed in linear time
    while (i< size) :

      if(str[start]!=str[end]) :

        #When not exist palindrome
        status=0
        break
      #Modify the start and end values
      start += 1
      end -=1 
      #When needed to check rotated string
      if((start)>size-1) :

      #Get new start
        start=0
      if(end<0) :

      #Get new end
        end=size-1

      i+=1
    return  status
  def find(self,str,size) :

    if(size<=1) :

      return
    j=0
    result=0
    status=0
    x=0
    y=0
    i=0
    while ( i<size) :

      #if i and j values are same then possible 
      #string contain palindrome
      if(str[i]==str[j]) :

        #check palindrome
        status=self.palindrome(str,i,j,size)
      if(status==1) :

         #when get palindrome 
        x=i
        y=j
        break
      #When needed to check palindrome in rotated string
      j=i
      i+=1
    if(status==1) :

      print (str,end=" : ")
      #palindrome sequence
      while(x!=y) :

        print (str[x],end=" ")
        x += 1
        if(x==size) :

          x=0
      print (str[y],end=" ")# last element
      print ("\n")
    else  :

      #When string is not a palindrome
      print (str,": Not a rotational palindrome\n")
  
def main():

  obj = MyString()
  str1="BAABACCCCCCCCCA"
  size=0
  size=len(str1)
  obj.find(str1,size)  #ABACCCCCCCCCABA  
  str2="BAABCC"
  size=len(str2)
  obj.find(str2,size)  #ABCCBA
  str3="CBAABCD"
  size=len(str3)
  obj.find(str3,size)   #ABCDCBA
  str4="BABE"
  size=len(str4)
  obj.find(str4,size)  #Not a Rotated palindrome
  str5="BAAB"
  size=len(str5)
  obj.find(str5,size) #ABBA
 
if __name__ =="__main__":
  main()

Output

BAABACCCCCCCCCA : A B A C C C C C C C C C A B A 

BAABCC : A B C C B A 

CBAABCD : A B C D C B A 

BABE : Not a rotational palindrome

BAAB : A B B A 
//C# program
//Display palindrome in rotated String
using System;
public class MyString
{

  //This function are capable to check palindrome in 
  //rotated and simple String using two index
  public int palindrome(String str,int start,int end,int size)
  {
    int status=1;


    //This loop is executed in linear time
    for (int i = 0; i < size ; ++i)
    {
      if(str[start]!=str[end])
      {
        //When not exist palindrome
        status=0;
        break;
      }
      //Modify the start and end values
      start++;
      end--;
      //When needed to check rotated String
      if((start)>size-1)
      {
        //Get new start
        start=0;
      }
      if(end<0)
      {
        //Get new end
        end=size-1;
      }
    }

    return status;
  }
  public void  find(String str,int size)
  {
    if(size<=1) return;
    int j=0,result=0;
    int status=0;
    int x=0,y=0;
    for (int i = 1; i <size; i++)
    {
      //if i and j values are same then possible 
      //String contain palindrome
      if(str[i]==str[j])
      {
        //check palindrome
        status=palindrome(str,i,j,size);
      }

      if(status==1)
      {
        //when get palindrome 
        x=i;
        y=j;
        break;
      }
      //When needed to check palindrome in rotated String
      j=i;
    }
    if(status==1)
    {
      Console.Write(str+" : ");
      //palindrome sequence
      while(x!=y)
      {
        Console.Write(" "+str[x]);
        x++;
        if(x==size)
        {
          x=0;
        }
      }
      Console.Write(" "+str[y] );//last element
      Console.WriteLine();

    }
    else
    {
      //When String is not a palindrome
      Console.WriteLine(str+" : Not a rotational palindrome\n");
    }
  }

  public static void Main(String[] args) 
  {

    MyString obj = new MyString();


    String str1="BAABACCCCCCCCCA";
    int size=0;

    size=str1.Length;

    obj.find(str1,size);  //ABACCCCCCCCCABA  


    String str2="BAABCC";

    size=str2.Length;
    obj.find(str2,size);  //ABCCBA


    String str3="CBAABCD";

    size=str3.Length;
    obj.find(str3,size);   //ABCDCBA


    String str4="BABE";


    size=str4.Length;;
    obj.find(str4,size);  //Not a Rotated palindrome



    String str5="BAAB";


    size=str5.Length;
    obj.find(str5,size); //ABBA


  }
}

Output

BAABACCCCCCCCCA :  A B A C C C C C C C C C A B A
BAABCC :  A B C C B A
CBAABCD :  A B C D C B A
BABE : Not a rotational palindrome

BAAB :  A B B A

<?php
//Php program 
//Display palindrome in rotated string

class MyString
{

  //This function are capable to check palindrome in 
  //rotated and simple string using two index
  function palindrome($str,$start,$end,$size)
  {
    $status=1;


    //This loop is executed in linear time
    for ($i=0; $i< $size;++ $i)
    {
      if($str[$start]!=$str[$end])
      {
        //When not exist palindrome
        $status=0;
        break;
      }
      //Modify the start and end values
      $start++;
      $end--;
      //When needed to check rotated string
      if(($start)>$size-1)
      {
      //Get new start
        $start=0;
      }
      if($end<0)
      {
      //Get new end
        $end=$size-1;
      }
    }

    return  $status;
  }
  function  find($str,$size)
  {
    if($size<=1)
    {
      return;
    }
    $j=0;
    $result=0;
    $status=0;
    $x=0;
    $y=0;
    for ($i=1; $i<$size; $i++)
    {
      //if i and j values are same then possible 
      //string contain palindrome
      if($str[$i]==$str[$j])
      {
      //check palindrome
        $status=$this->palindrome($str,$i,$j,$size);
      }

      if($status==1)
      {
       //when get palindrome 
        $x=$i;
        $y=$j;
        break;
      }
      //When needed to check palindrome in rotated string
      $j=$i;
    }
    if($status==1)
    {
      echo  $str." : ";
      //palindrome sequence
      while($x!=$y)
      {
        echo " ".$str[$x];
        $x++;
        if($x==$size)
        {
          $x=0;
        }
      }
    echo " ".($str[$y]);// $last $element
    echo ("\n");

  }
  else 
  {
      //When string is not a palindrome
    echo  $str.": Not a rotational palindrome\n";
  }
}

}
function main()
{

  $obj= new MyString();
  $str1="BAABACCCCCCCCCA";
  $size=0;


  $size=strlen($str1);

  $obj->find($str1,$size);  //ABACCCCCCCCCABA  


  $str2="BAABCC";

  $size=strlen($str2);
  $obj->find($str2,$size);  //ABCCBA

  
  $str3="CBAABCD";

  $size=strlen($str3);
  $obj->find($str3,$size);   //ABCDCBA


  $str4="BABE";


  $size=strlen($str4);
  $obj->find($str4,$size);  //Not a Rotated palindrome



  $str5="BAAB";


  $size=strlen($str5);
  $obj->find($str5,$size);; //ABBA
}
main();
?>

Output

BAABACCCCCCCCCA :  A B A C C C C C C C C C A B A
BAABCC :  A B C C B A
CBAABCD :  A B C D C B A
BABE: Not a rotational palindrome
BAAB :  A B B A

Time Complexity:

The time complexity of this code is primarily determined by the size of the input string. Let's denote the size of the string as "n".

The function "palindrome" iterates through the characters of the string in a linear manner, performing constant-time operations. Therefore, its time complexity is O(n).

The function "find" also iterates through the characters of the string in a linear manner, calling the "palindrome" function for each index. Hence, its time complexity is O(n^2) in the worst case, as the "palindrome" function is called for each index.

The main function calls the "find" function for each given string, which results in a constant number of calls. Therefore, the overall time complexity of the code remains O(n^2).

By following this approach, we can successfully identify palindromes in rotated strings using the provided code. Understanding the problem, implementing the algorithm, and analyzing the time complexity can help us solve similar problems effectively.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment