Form String by Rotation

Determine if one string can be obtained by rotating another string

Understand the Problem

Problem Statement

Given two strings S1 and S2, print Yes if S2 can be obtained by rotating the string S1. Else print No.

Constraints

1 ≤ Length of S1, S2 ≤ 10000
String length must be equal for rotation to be possible
Strings contain only printable ASCII characters
Time complexity should be O(n) where n is the string length

Examples

Example 1

Input

hello llohe

Output

Yes

Explanation

S2 "llohe" can be obtained by rotating S1 "hello" left by 2 positions. Alternatively, "llohe" appears as a substring in "hellohello" starting at index 2.

Example 2

Input

Question tionseuQ

Output

No

Explanation

S2 "tionseuQ" cannot be obtained by rotating S1 "Question". The string "tionseuQ" does not appear as a substring in "QuestionQuestion".

Solution

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

int areRotations(char* s1, char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    
    // If lengths are different, rotation is impossible
    if (len1 != len2) {
        return 0;
    }
    
    // Create temp string by concatenating s1 with itself
    char* temp = (char*)malloc(2 * len1 + 1);
    strcpy(temp, s1);
    strcat(temp, s1);
    
    // Check if s2 is substring of temp
    if (strstr(temp, s2) != NULL) {
        free(temp);
        return 1;
    }
    
    free(temp);
    return 0;
}

int main() {
    char s1[10001], s2[10001];
    scanf("%s %s", s1, s2);
    
    if (areRotations(s1, s2)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    
    return 0;
}

Time:O(n) where n is the length of the strings

Space:O(n) for the temporary concatenated string

Approach:

The C solution implements the concatenation approach:

First checks if string lengths are equal using strlen()
Allocates memory for a temporary string that can hold s1+s1
Uses strcpy() and strcat() to concatenate s1 with itself
Uses strstr() to check if s2 appears as a substring in the concatenated string
Properly frees allocated memory and returns appropriate result

Visual Explanation

Loading diagram...

All Problems