49. Check if a String Is a Rotation of Another String

Given two strings s1 and s2 of equal length, print 'Yes' if s2 can be obtained by rotating s1 by some number of positions, otherwise print 'No'.

Input: The first line contains string s1. The second line contains string s2, of equal length to s1. Output: Print 'Yes' if s2 is a rotation of s1, otherwise print 'No'.

1 <= |s1| = |s2| <= 10^5

Checking the lengths match FIRST is essential - without it, a shorter s2 could accidentally be found as a substring of s1+s1 without genuinely being a full rotation.

Check whether one string can be turned into another simply by rotating it - moving some characters from the front to the back (or back to front) without reordering them otherwise. Brute force: Try every possible rotation of s1 directly (shifting it by 1, 2, 3, ... positions) and compare each to s2 - this costs O(n²) in the worst case, since generating and comparing each rotation takes O(n). Optimised: The elegant trick 's2 is a rotation of s1 if and only if s2 is a substring of s1+s1' avoids generating every rotation individually - doubling s1 naturally contains all its rotations as substrings, so a single efficient substring search (like KMP, in O(n)) settles the question directly.

Concatenate s1 with itself and run the Knuth-Morris-Pratt algorithm to search for s2 inside s1+s1: precompute s2's failure/prefix function in O(n) time, then scan s1+s1 once, using the failure function to skip re-comparisons after a mismatch instead of restarting from scratch. This guarantees worst-case linear time with no dependence on hash collisions, making it both asymptotically optimal and deterministic, unlike the probabilistic rolling-hash approach. Time: O(n) Space: O(n)

Instead of materializing every rotation, concatenate s1 with itself (s1+s1) and search for s2 as a substring of that concatenation using a rolling polynomial hash: compute s2's hash once, then slide a window of length n across s1+s1 updating the window hash in O(1) per shift and comparing it to s2's hash. A hash match is (almost certainly) a true match, verified with a direct character comparison only when hashes collide. This avoids rebuilding/comparing full strings at every offset, giving expected linear time. Time: O(n) expected Space: O(n)

Generate every possible rotation of s1 by repeatedly moving its first character to the end (or by slicing at each offset) and directly compare the resulting string to s2. If any of the |s1| rotations matches exactly, the answer is Yes. This is correct because every rotation is explicitly constructed and checked, but constructing and comparing a full-length string at each of the n offsets costs O(n) work per offset. Time: O(n^2) Space: O(n)

1. First check the two strings have equal length - if not, immediately answer No. 2. Concatenate the first string with itself (doubling it), which contains EVERY possible rotation of it as a substring somewhere within. 3. Check whether the second string appears anywhere inside that doubled string - if so, it's a valid rotation.

Time: O(n) using an efficient substring search algorithm (like KMP) on the doubled string; O(n²) with a naive substring search, though still far better than generating every rotation explicitly. Space: O(n), for the doubled string.

s1 equal to s2 (a zero-position rotation, 'Yes'); s2 containing the same characters as s1 but not a valid rotation ('No'); strings up to 10^5 characters for performance.

The 's1+s1 contains every rotation' trick is a classic, elegant one-liner insight - be ready to explain WHY it works (any rotation point becomes a valid starting position within the doubled string) rather than just stating it.