String rotation is a common algorithmic problem that appears in coding interviews and real-world applications. A string rotation occurs when you take some characters from the beginning of a string and move them to the end, or vice versa.
For example, if you start with "abcdef" and move the first three characters ("abc") to the end, you get "defabc". Both strings contain the same characters in the same relative order, just with a different starting point.
The naive approach would be to generate all possible rotations of one string and check if any match the other string. However, this requires O(n²) time complexity, which becomes inefficient for longer strings.
The elegant solution uses a clever insight: if string A is a rotation of string B, then A will appear as a substring within B concatenated with itself (B + B). This works because when you concatenate B with itself, you create a string that contains every possible rotation of B as a contiguous substring.
This approach has several advantages: it's simple to implement, runs in O(n) time (assuming the substring search is optimized), and handles all edge cases naturally. You still need to check that both strings have the same length first, since rotations must preserve the total number of characters.
The concatenation trick is widely used in string processing algorithms and demonstrates how a non-obvious mathematical insight can dramatically simplify a problem.
1def find_all_rotations(s):
2 """Generate all possible rotations of a string"""
3 if not s:
4 return [s]
5
6 rotations = []
7 for i in range(len(s)):
8 # Take characters from position i to end, plus beginning to i
9 rotation = s[i:] + s[:i]
10 rotations.append(rotation)
11
12 return rotations
13
14# Example usage
15original = "abcd"
16all_rotations = find_all_rotations(original)
17print(f"Rotations of '{original}': {all_rotations}")
18# Output: ['abcd', 'bcda', 'cdab', 'dabc']
19
20# Now see the concatenation insight
21doubled = original + original # "abcdabcd"
22print(f"Doubled string: '{doubled}'")
23# Notice: every rotation appears as a substring in the doubled string!