Scribd
Upload
13 views4 pages

String Rotation Anagram Checker

The document describes a problem of rotating a string in specified directions and magnitudes, then checking if the accumulated first characters of the rotated strings form an anagram of any substring of the original string. It includes constraints on the string length and the number of operations, as well as a sample input and output. A possible solution is provided in C++ code, detailing functions for string rotation and anagram checking.

Uploaded by

101ARNAB CHAKRABORTY
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views4 pages

String Rotation Anagram Checker

The document describes a problem of rotating a string in specified directions and magnitudes, then checking if the accumulated first characters of the rotated strings form an anagram of any substring of the original string. It includes constraints on the string length and the number of operations, as well as a sample input and output. A possible solution is provided in C++ code, detailing functions for string rotation and anagram checking.

Uploaded by

101ARNAB CHAKRABORTY
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

String Rotation

Problem Description
Rotate a given String in the specified direction by specified magnitude.
After each rotation make a note of the first character of the rotated String, after all rotation are
performed the accumulated first character as noted previously will form another string,
say FIRSTCHARSTRING.
Check If FIRSTCHARSTRING is an Anagram of any substring of the Original string.
If yes print "YES" otherwise "NO". Input
The first line contains the original string s. The second line contains a single integer q. The
ith of the next q lines contains character d[i] denoting direction and integer r[i] denoting the
magnitude.

Constraints
1 <= Length of original string <= 30
1<= q <= 10

Output
YES or NO
Explanation
Example 1
Input
carrace
3
L2
R2
L3
Output
NO
Explanation
After applying all the rotations, the FIRSTCHARSTRING string will be "rcr" which is not anagram
of any sub string of original string "carrace".
Possible Solution:
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
//function for string reverse of specified ranege
void reverse(char str[], int start, int end){
while (start < end){
char temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}

//function for left rotation


void leftRotate(char str[], int d) {
int len=strlen(str);
reverse(str, 0, d-1);
reverse(str, d, len-1);
reverse(str, 0, len-1);
return;
}

//function for right rotation


void rightRotate(char str[], int d) {
leftRotate(str, strlen(str)-d);
return;
}

void swap(char* a, char* b){


char t = *a;
*a = *b;
*b = t;
}

void bubbleSort(char str[]){


int i, j;
int n=strlen(str);
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (str[j] > str[j+1])
swap(&str[j], &str[j+1]);
}

int checkAnagram(char str[],char str1[]){


int len=strlen(str); //Checking for anagram
int len1=strlen(str1);
cout<<str1<<endl;
bubbleSort(str1); //sort generated string
int i,j;
char str2[11];
for (i = 0; i <= len - len1; i++){ //find all substring of
length len1
for (j = 0; j <len1; j++)
str2[j] =str[i+j];
str2[j]='\0';
bubbleSort(str2); //sort a substing of original string
if(!strcmp(str1,str2)) return 1; //Anagram found
}
return 0; //Anagram not found
}

int main(){
char originalString[50];
char str[50];
char str1[11];

cin>>originalString; // Read input string


int noOfOperation;
cin>>noOfOperation; //Read number
int i, j=0;
strcpy(str,originalString); //unchanged the original
string
for(int i=1;i<=noOfOperation;i++){
char direction;
int offset;
cin>>direction>>offset; //read
direction and magnitude
if(direction=='L') //For
rotation
leftRotate(str, offset);
else if(direction=='R')
rightRotate(str,offset);
else return 1;
str1[j]=str[0]; str1[++j]='\0'; //generate FIRST
CHARACTER String
}
//check angram for all subsstring of original string
if(checkAnagram(originalString,str1)) cout<<"YES";
else cout<<"No";

return 0;
}

You might also like