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.

Categories
Relative Post