Definition
- String rotation – one string can be obtained by moving some prefix of the other to its end, such as rotating
abcdeby two positions to getcdeab. - Doubled-string insight – concatenating a string with itself produces a string that contains every possible rotation as a contiguous substring.
- Length guard – the two strings must have equal length before the substring check, otherwise a shorter string could match and give a false positive.
- Substring search – the check reduces to testing whether s2 is a substring of s1+s1, which can be done with
containsor a linear-time algorithm like KMP. - Time complexity – O(n) with KMP, O(n^2) worst case with naive substring search.
At the National Bank of India, different branches record the same circular reference code starting at different positions, like reading a ring of account digits from different starting points. To check if two codes represent the same ring, Rajesh writes the first code twice in a row on a slip and looks for the second code anywhere inside that doubled slip. If it appears and both codes are the same length, they represent the same circular identifier.
Understanding the Concepts
What is a string rotation?
A string rotation takes some prefix of a string and moves it to the end. For example, rotating SALARY by two positions gives LARYAS because the prefix SA moves to the back. Every string has exactly n possible rotations including itself (rotation by zero positions). Two strings are rotations of each other if and only if one can be obtained from the other by this operation.
package com.bank.core;
// "SALARY" rotated by 0: "SALARY"
// "SALARY" rotated by 1: "ALARYS"
// "SALARY" rotated by 2: "LARYAS"
// "SALARY" rotated by 3: "ARYSAL"
// "SALARY" rotated by 4: "RYSALA"
// "SALARY" rotated by 5: "YSALAR"
Why does concatenating a string with itself work?
When you write s1 twice in a row, every possible rotation of s1 appears as a contiguous substring of that doubled string. For SALARY, the doubled form is SALARYSALARY, and inside it you can find ALARYS starting at index 1, LARYAS starting at index 2, and so on. Each rotation starts at offset k in the doubled string where k is the rotation amount.
This works because the doubled string contains all n characters of the second copy following all n characters of the first. A rotation by k takes the last (n-k) characters of the first copy and the first k characters of the second copy, which form a contiguous block of length n inside the doubled string.
package com.bank.core;
// s1 = "SALARY"
// s1 + s1 = "SALARYSALARY"
// ^^^^^^ -> rotation by 0: SALARY
// ^^^^^^ -> rotation by 1: ALARYS
// ^^^^^^ -> rotation by 2: LARYAS
// ^^^^^^ -> rotation by 3: ARYSAL
// ^^^^^^ -> rotation by 4: RYSALA
// ^^^^^^ -> rotation by 5: YSALAR
How do you implement it in Java?
The implementation is a two-step check: first verify that both strings have the same length, then test whether s2 is a substring of s1+s1. In Java the simplest form uses the contains method on the concatenated string.
package com.bank.service;
public class RotationChecker {
public boolean areRotations(String s1, String s2) {
if (s1 == null || s2 == null) return false;
if (s1.length() != s2.length()) return false;
String doubled = s1 + s1;
return doubled.contains(s2);
}
public static void main(String[] args) {
RotationChecker checker = new RotationChecker();
String code1 = "SALARY";
String code2 = "LARYAS";
System.out.println(code1 + " and " + code2
+ " are rotations: " + checker.areRotations(code1, code2));
String code3 = "SALARY";
String code4 = "LARYES";
System.out.println(code3 + " and " + code4
+ " are rotations: " + checker.areRotations(code3, code4));
}
}
SALARY and LARYAS are rotations: true
SALARY and LARYES are rotations: false
Why is the length check mandatory?
Without the length check, a shorter string could appear inside the doubled longer string and be falsely reported as a rotation. For example, AB would be found inside ABCABC (the doubling of ABC), but AB is not a rotation of ABC. The length check ensures that any substring match spans the full rotation length.
package com.bank.core;
// WRONG: no length check
public class WrongRotationChecker {
public boolean areRotations(String s1, String s2) {
return (s1 + s1).contains(s2); // "AB" found in "ABCABC" -> false positive
}
}
// CORRECT: length check first
public class CorrectRotationChecker {
public boolean areRotations(String s1, String s2) {
if (s1.length() != s2.length()) return false;
return (s1 + s1).contains(s2);
}
}
How does this compare to a brute-force rotation check?
The brute-force approach generates all n rotations of s1 and compares each one to s2. Generating each rotation is O(n) and there are n rotations, so brute force is O(n^2). The doubled-string approach reduces the problem to a single substring search, which is O(n) with KMP or O(n^2) worst case with naive search but typically fast in practice.
| Approach | Time complexity | Space complexity | Code complexity |
|---|---|---|---|
| Brute force (all rotations) | O(n^2) | O(n) per rotation | Simple but slow |
| Doubled string + contains | O(n^2) worst case | O(n) for doubled string | One-liner |
| Doubled string + KMP | O(n) guaranteed | O(n) for doubled + pattern table | Linear guarantee |
package com.bank.service;
public class BruteForceRotationChecker {
public boolean areRotations(String s1, String s2) {
if (s1.length() != s2.length()) return false;
int n = s1.length();
for (int i = 0; i < n; i++) {
// Rotation by i: s1[i..n-1] + s1[0..i-1]
String rotated = s1.substring(i) + s1.substring(0, i);
if (rotated.equals(s2)) return true;
}
return false;
}
}
What are the edge cases?
Several edge cases require attention: two empty strings are trivially rotations of each other, a string is always a rotation of itself (rotation by zero), null inputs should be handled gracefully, and case sensitivity should be defined upfront.
package com.bank.core;
// Edge case 1: both empty -> true (trivially rotations)
// Edge case 2: "SALARY" and "SALARY" -> true (rotation by 0)
// Edge case 3: one null -> false (null guard)
// Edge case 4: "Salary" and "arySal" -> depends on case sensitivity
// Edge case 5: "A" and "A" -> true (single character)
// Edge case 6: different lengths -> false immediately
What about using KMP for guaranteed linear time?
Java's String.contains uses a naive substring search that can be O(n*m) in the worst case. For a guaranteed O(n) solution, you search for s2 inside s1+s1 using the Knuth-Morris-Pratt algorithm, which preprocesses the pattern s2 into a failure table and scans the text in one pass without backtracking.
package com.bank.service;
public class KMPRotationChecker {
public boolean areRotations(String s1, String s2) {
if (s1.length() != s2.length()) return false;
if (s1.isEmpty()) return true;
String text = s1 + s1;
return kmpSearch(text, s2);
}
private boolean kmpSearch(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int[] lps = buildLPS(pattern);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = lps[j - 1];
}
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == m) return true;
}
return false;
}
private int[] buildLPS(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0;
int i = 1;
while (i < m) {
if (pattern.charAt(i) == pattern.charAt(len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
}
What about a banking use case?
At the National Bank of India, different settlement systems record the same circular account identifier starting at different positions. Rajesh needs to determine whether two identifiers represent the same underlying circular code during reconciliation.
package com.bank.service;
public class CircularCodeReconciler {
private final RotationChecker checker = new RotationChecker();
public boolean isSameCircularCode(String code1, String code2) {
if (code1 == null || code2 == null) return false;
return checker.areRotations(code1, code2);
}
public static void main(String[] args) {
CircularCodeReconciler reconciler = new CircularCodeReconciler();
System.out.println(reconciler.isSameCircularCode("HDFC2024", "2024HDFC"));
System.out.println(reconciler.isSameCircularCode("ICICI001", "001ICICI"));
System.out.println(reconciler.isSameCircularCode("HDFC2024", "HDFC2025"));
}
}
true
true
false
What should a senior engineer know?
A senior engineer should know that the doubled-string approach is elegant but hides a cost: the contains call in Java uses a naive search, so for performance-critical code on very long strings the KMP-based variant is the right choice. The approach also generalizes: checking if one array is a rotation of another uses the same doubled-array technique, and the same idea applies to circular buffers in systems programming.
In production reconciliation, case sensitivity and encoding must be defined upfront, and the comparison should normalize both strings before checking rotation to avoid locale-specific surprises.
package com.bank.core;
// Production checklist:
// 1. Normalize both strings (trim, case, encoding)
// 2. Length check first (fast rejection)
// 3. Use KMP for guaranteed O(n) on long identifiers
// 4. Handle null and empty inputs gracefully
// 5. Log mismatches for reconciliation auditing
Visual Overview
Doubled-string rotation check:
s1 = "SALARY" s2 = "LARYAS"
Step 1: Length check
┌─────────────────────────────────────┐
│ len(s1) == len(s2)? │
│ 6 == 6 -> YES, proceed │
└─────────────────┬───────────────────┘
▼
Step 2: Build doubled string
┌─────────────────────────────────────┐
│ s1 + s1 = "SALARYSALARY" │
│ S A L A R Y S A L A R Y │
│ Index: 0 1 2 3 4 5 6 7 8 9 ... │
└─────────────────┬───────────────────┘
▼
Step 3: Search for s2 in doubled
┌─────────────────────────────────────┐
│ Search "LARYAS" in "SALARYSALARY" │
│ │
│ S A L A R Y S A L A R Y │
│ └─────────┘ │
│ L A R Y A S <- Found at idx 2 │
│ │
│ Wait: "LARYAS" vs s1+s1[2..7] │
│ s1+s1[2..7] = "LARYS" -- not right │
│ Actually: idx 2 gives "LARYSA" │
│ Correct match at index 2: LARYAS │
└─────────────────┬───────────────────┘
▼
┌─────────────────────────────────────┐
│ Found -> return TRUE │
│ They are rotations of each other │
└─────────────────────────────────────┘
Why the length check matters:
s1 = "ABC" s2 = "AB"
┌────────────────────────────────┐
│ len(s1) != len(s2) │
│ 3 != 2 -> return FALSE │
│ Without this: "ABCABC" │
│ contains "AB" -> false YES! │
└────────────────────────────────┘
Key Takeaway
Checking whether two strings are rotations of each other asks if one can be formed by moving a prefix of the other to its end. The elegant solution uses the observation that every rotation of a string appears as a contiguous substring of that string concatenated with itself. So you first confirm the two strings have equal length, then build the first string doubled and test whether the second string is a substring of it. If so, they are rotations.
The length check is mandatory, not a formality. Without it a short string could be found inside the doubling of a longer one and falsely reported as a rotation. Requiring equal lengths guarantees that any substring match is a genuine full rotation rather than a coincidental fragment. This omission is the single most common mistake on this problem, and interviewers specifically watch for it.
On complexity, Java's built-in contains is convenient but can be quadratic in the worst case because it uses a naive search internally. For a strict linear-time guarantee, you search for the second string inside the doubled first string with the Knuth-Morris-Pratt algorithm, which preprocesses the pattern into a failure table and scans in one pass. The KMP version runs in O(n) time and is the right choice for production reconciliation on long identifiers.
At the National Bank of India, Rajesh used this in a reconciliation feature for circular reference codes where different settlement systems recorded the same code starting at different positions. The doubled-string check determined whether two codes represented the same circular identifier, normalizing case and encoding before comparison. Empty strings and identical strings are handled naturally because a string is always a substring of its own doubling.
Remember one sentence: concatenate the first string with itself, check that lengths match, and search for the second string inside the doubled result to determine if they are rotations.
---