Backend interview prep

Start Learning

Check Rotation of Strings

Java coding interview problem for String Coding: Check Rotation of Strings.

Checking whether one string is a rotation of another is one of the most popular Java String interview questions.

Although the problem looks easy, it evaluates several important programming concepts, including:

  • String Manipulation
  • String Concatenation
  • Substring Search
  • Pattern Matching
  • KMP Algorithm
  • Time Complexity
  • Space Complexity

Interviewers often ask several follow-up questions such as:

  • Can you solve it without using contains()?
  • Can you solve it in linear time?
  • What is the optimal solution?
  • Can you implement KMP?
  • What is left rotation and right rotation?

Learning multiple approaches prepares you for all these interview variations.

Problem Statement

Given two strings A and B, determine whether B is a rotation of A.

Return:

  • true if B is a rotation of A.
  • false otherwise.

Both strings must have the same length.

Example 1

Input

A = ABCD

B = CDAB

Output

true

Example 2

Input

A = waterbottle

B = erbottlewat

Output

true

Example 3

Input

A = Java

B = avaJ

Output

true

Example 4

Input

A = Hello

B = World

Output

false

What is String Rotation?

A string rotation means moving characters from one end of the string to the other while preserving their order.

Example

Original

ABCD

Rotate Left Once

BCDA

Rotate Again

CDAB

Rotate Again

DABC

Rotate Again

ABCD

After four rotations we return to the original string.

Another Example

Original

Java

Possible Rotations

Java

avaJ

vaJa

aJav

All of these are valid rotations.

Why is this Question Asked in Interviews?

This problem helps interviewers evaluate whether candidates understand:

  • String Searching
  • Substrings
  • Pattern Matching
  • String Concatenation
  • Algorithm Optimization
  • KMP Algorithm
  • Time Complexity

It is also the foundation for many advanced interview problems.

Examples include:

  • Pattern Matching
  • Circular Arrays
  • KMP Algorithm
  • Rabin-Karp
  • String Matching

Real-World Applications

String rotation has several practical applications.

Circular Buffers

Operating systems use circular buffers for efficient memory management.

Network Packet Processing

Rotating buffers improves packet handling performance.

Cryptography

Some encryption algorithms rotate characters before encoding.

Text Editors

Editors support circular text transformations.

Scheduling Systems

Round-robin scheduling uses circular rotation concepts.

Understanding String Rotation

Suppose we have

ABCDE

Rotate once

BCDEA

Rotate again

CDEAB

Rotate again

DEABC

Rotate again

EABCD

Every rotation preserves

  • All characters
  • Same length
  • Same order (cyclic)

Left Rotation vs Right Rotation

These two concepts are frequently asked in interviews.

Left Rotation

Input

ABCDE

Rotate Left

BCDEA

Character

A

moves to the end.

Right Rotation

Input

ABCDE

Rotate Right

EABCD

Character

E

moves to the beginning.

Mathematical Concept

Consider

ABCD

Concatenate

ABCDABCD

Now search

CDAB

It exists.

Therefore

CDAB

is a rotation.

Another Example

waterbottle

Concatenate

waterbottlewaterbottle

Search

erbottlewat

Found.

Result

true

Visual Representation

Original

ABCD

Double String

ABCDABCD

Search

CDAB

Visualization

ABCDABCD
  └────┘
   CDAB

Found.

Return

true

Dry Run

Input

A = ABCD

B = CDAB

Step 1

Check lengths.

4

4

Equal.

Step 2

Concatenate

ABCDABCD

Step 3

Search

CDAB

Found.

Return

true

Another Example

Input

A = ABCD

B = ACBD

Concatenate

ABCDABCD

Search

ACBD

Not Found.

Return

false

Approach 1 — Using String Concatenation (Recommended)

This is the simplest and most commonly asked interview solution.

The idea is:

  • Both strings must have equal length.
  • Concatenate the first string with itself.
  • If the second string exists inside the concatenated string, it is a rotation.

Why Does This Work?

Example

ABCD

Double String

ABCDABCD

Possible Rotations

ABCD

BCDA

CDAB

DABC

Every possible rotation appears inside the doubled string.

Algorithm

  1. Compare lengths.
  2. Concatenate the first string with itself.
  3. Search for the second string.
  4. Return the result.

Java Program

public class StringRotation {

    public static boolean isRotation(String first,
                                     String second) {

        if (first.length() != second.length()) {
            return false;
        }

        String combined = first + first;

        return combined.contains(second);

    }

    public static void main(String[] args) {

        System.out.println(
                isRotation("ABCD", "CDAB"));

        System.out.println(
                isRotation("Java", "avaJ"));

        System.out.println(
                isRotation("Hello", "World"));

    }

}

Output

true

true

false

Step-by-Step Code Explanation

Check the lengths.

if (first.length() != second.length())

Different lengths can never be rotations.

Concatenate.

String combined = first + first;

Example

ABCD

↓

ABCDABCD

Search.

combined.contains(second)

If found

true

Otherwise

false

Dry Run of Concatenation Approach

Input

ABCD

DABC
Step Value
Original ABCD
Double ABCDABCD
Search DABC
Found? Yes
Answer true

Advantages

  • Very easy to understand.
  • Most common interview solution.
  • Minimal code.
  • Excellent readability.
  • Frequently accepted in coding interviews.

Drawbacks

  • Uses additional memory for the concatenated string.
  • Internally depends on substring search.
  • Interviewers may ask for a solution without using contains().

Approach 2 — Manual Rotation Check

Instead of using contains(), we can manually generate every possible rotation and compare it with the target string.

Although this approach is not optimal, it demonstrates a clear understanding of rotations.

Algorithm

  1. Check string lengths.
  2. Rotate the string one character at a time.
  3. Compare each rotation with the second string.
  4. Return true if a match is found.
  5. Otherwise return false.

Java Program

public class ManualRotation {

    public static boolean isRotation(String first,
                                     String second) {

        if (first.length() != second.length()) {
            return false;
        }

        String rotated = first;

        for (int i = 0; i < first.length(); i++) {

            if (rotated.equals(second)) {
                return true;
            }

            rotated = rotated.substring(1)
                    + rotated.charAt(0);

        }

        return false;

    }

    public static void main(String[] args) {

        System.out.println(
                isRotation("ABCD", "CDAB"));

        System.out.println(
                isRotation("Hello", "World"));

    }

}

Output

true

false

Step-by-Step Code Explanation

Store the original string.

String rotated = first;

Rotate once.

rotated = rotated.substring(1)
        + rotated.charAt(0);

Example

ABCD

↓

BCDA

Compare.

rotated.equals(second)

If equal,

return

true

Otherwise continue rotating.

Time & Space Complexity

Approach Time Extra Space
String Concatenation + contains() O(n) O(n)
Manual Rotation O(n²) O(n)

Where:

  • n = length of the string.

Comparison of Approaches

Feature Concatenation Manual Rotation
Interview Friendly ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐
Easy to Understand ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Performance ⭐⭐⭐⭐⭐ ⭐⭐⭐
Uses Built-in APIs ✅ ❌

Advantages

  • Both approaches are easy to understand.
  • Concatenation is concise and commonly accepted in interviews.
  • Manual Rotation helps explain the concept of cyclic shifts.
  • Both preserve the order of characters during rotation.

Drawbacks

  • Concatenation allocates an additional string.
  • Manual Rotation performs repeated string creation, making it slower.
  • Neither approach is the most optimized for advanced substring-search scenarios.

In Part 2, we'll cover:

  • Approach 3 – Using StringBuilder
  • Approach 4 – Using KMP (Knuth-Morris-Pratt) Algorithm
  • Approach 5 – Rolling Hash (Rabin-Karp Concept)
  • Left Rotation vs Right Rotation with K Rotations
  • Unicode Considerations
  • Comparison of All Approaches
  • Common Interview Mistakes
  • Edge Cases
  • Interview Follow-up Questions
  • Related Problems
  • Key Takeaways
  • Frequently Asked Interview Questions
  • Interview Tips

Approach 3 — Using StringBuilder

Instead of creating new strings repeatedly, we can use a StringBuilder for rotations.

StringBuilder is mutable, making repeated modifications more efficient than repeatedly creating new String objects.

Algorithm

  1. Check whether both strings have the same length.
  2. Create a StringBuilder.
  3. Rotate left one character at a time.
  4. Compare after every rotation.
  5. Return the result.

Java Program

public class RotationUsingStringBuilder {

    public static boolean isRotation(String first,
                                     String second) {

        if (first.length() != second.length()) {
            return false;
        }

        StringBuilder builder = new StringBuilder(first);

        for (int i = 0; i < first.length(); i++) {

            if (builder.toString().equals(second)) {
                return true;
            }

            char firstCharacter = builder.charAt(0);

            builder.deleteCharAt(0);

            builder.append(firstCharacter);

        }

        return false;

    }

    public static void main(String[] args) {

        System.out.println(
                isRotation("ABCD", "CDAB"));

    }

}

Output

true

Advantages

  • Better than repeated string concatenation.
  • Demonstrates StringBuilder.
  • Easy to understand.

Drawbacks

  • Still performs multiple rotations.
  • Slower than substring-search algorithms.

Approach 4 — Using KMP (Knuth-Morris-Pratt) Algorithm

Interviewers sometimes ask:

Can you solve this without using contains()?

A classic answer is the KMP (Knuth-Morris-Pratt) algorithm.

Instead of using Java's built-in search,

we search the doubled string manually.

Why KMP?

Suppose

ABCDABCD

Search

CDAB

Instead of restarting comparisons repeatedly,

KMP reuses previous comparisons using the LPS (Longest Prefix Suffix) array.

This provides linear time searching.

Algorithm

  1. Compare lengths.
  2. Concatenate the first string.
  3. Build the LPS array.
  4. Search using KMP.
  5. Return the result.

Simplified Java Program

public class RotationUsingKMP {

    public static boolean isRotation(String first,
                                     String second) {

        if (first.length() != second.length()) {
            return false;
        }

        String combined = first + first;

        return kmpSearch(combined, second);

    }

    private static boolean kmpSearch(String text,
                                     String pattern) {

        return text.contains(pattern);

    }

}

Note: In production or interview settings, kmpSearch() would implement the full KMP algorithm using an LPS (Longest Prefix Suffix) table instead of delegating to contains(). The complete KMP implementation is typically covered separately because of its size.

Advantages

  • Linear-time searching.
  • Excellent interview discussion.
  • Used in pattern matching.

Drawbacks

  • Complex implementation.
  • Requires understanding of the LPS array.

Approach 5 — Rolling Hash (Rabin-Karp Concept)

Another interview discussion is the Rabin-Karp algorithm.

Instead of comparing characters directly,

compare hash values.

Idea

Compute

Hash("CDAB")

Compare it with every substring hash inside

ABCDABCD

If the hashes match,

verify the characters.

Advantages

  • Efficient for multiple searches.
  • Excellent interview topic.

Drawbacks

  • Hash collisions are possible.
  • More difficult to implement correctly.

Left Rotation vs Right Rotation

Interviewers often ask the difference.

Left Rotation

Input

ABCDE

Rotate Left by 2

CDEAB

Formula

substring(k)

+

substring(0, k)

Java Program

public class LeftRotation {

    public static String rotateLeft(String word, int k) {

        k %= word.length();

        return word.substring(k)
                + word.substring(0, k);

    }

    public static void main(String[] args) {

        System.out.println(
                rotateLeft("ABCDE", 2));

    }

}

Output

CDEAB

Right Rotation

Input

ABCDE

Rotate Right by 2

DEABC

Formula

substring(length - k)

+

substring(0, length - k)

Java Program

public class RightRotation {

    public static String rotateRight(String word, int k) {

        k %= word.length();

        return word.substring(word.length() - k)
                + word.substring(0, word.length() - k);

    }

    public static void main(String[] args) {

        System.out.println(
                rotateRight("ABCDE", 2));

    }

}

Output

DEABC

Unicode Considerations

Java strings support Unicode.

Examples

こんにちは

नमस्ते

😊Hello

The concatenation and rotation logic works for general Java strings.

However, if your application must correctly handle supplementary Unicode characters (such as many emoji), consider processing Unicode code points instead of individual char values.

Edge Cases

First String Second String Expected Output
"" "" true
"A" "A" true
"ABCD" "BCDA" true
"ABCD" "ACBD" false
"AAAA" "AAAA" true
null null Handle appropriately based on application requirements

Time & Space Complexity

Approach Time Extra Space
Concatenation + contains() O(n) O(n)
Manual Rotation O(n²) O(n)
StringBuilder Rotation O(n²) O(n)
KMP O(n) O(n)
Rolling Hash (Rabin-Karp) Average O(n) O(1)

Where:

  • n = length of the string.

Comparison of All Approaches

Approach Interview Friendly Performance Best Use Case
Concatenation + contains() ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ General interviews
Manual Rotation ⭐⭐⭐⭐ ⭐⭐⭐ Understanding rotations
StringBuilder ⭐⭐⭐⭐ ⭐⭐⭐ Mutable string operations
KMP ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ Pattern matching interviews
Rolling Hash ⭐⭐⭐ ⭐⭐⭐⭐ Multiple pattern searches

Common Interview Mistakes

Mistake 1

Not checking string lengths.

Wrong

combined.contains(second)

Correct

if (first.length() != second.length()) {
    return false;
}

Mistake 2

Checking substring before concatenation.

Wrong

ABCD

contains

CDAB

Always concatenate first.

Mistake 3

Confusing string reversal with string rotation.

Reverse

ABCD

↓

DCBA

Rotation

ABCD

↓

BCDA

These are different operations.

Mistake 4

Ignoring empty strings.

Always test

""

""

↓

true

Mistake 5

Using manual rotation when an O(n) solution is expected.

Mention the concatenation or KMP approach for better performance.

Interview Follow-up Questions

Q1. Can you solve it without using contains()?

Q2. Why does doubling the string work?

Q3. How does KMP improve substring searching?

Q4. What is the time complexity?

Q5. What is the difference between left and right rotation?

Q6. Can you rotate a string by k positions?

Q7. How would you support Unicode?

Q8. Can you solve this using Rolling Hash?

Q9. How would you rotate a character array in place?

Q10. Where are string rotations used in real-world systems?

Related Problems

  • Reverse String
  • Reverse Words in a String
  • String Anagram
  • Longest Common Prefix
  • Implement strStr()
  • KMP Pattern Matching
  • Rabin-Karp Algorithm
  • Rotate Array

Key Takeaways

  • Two strings are rotations if they have the same length and one appears as a substring of the other after doubling the original string.
  • The Concatenation + contains() approach is the simplest and most commonly accepted interview solution.
  • Manual Rotation demonstrates the concept of cyclic shifts but is less efficient.
  • StringBuilder avoids repeated immutable string creation but still performs repeated rotations.
  • KMP provides O(n) substring searching and is a common follow-up interview topic.
  • Rolling Hash (Rabin-Karp) is useful when searching for multiple patterns or discussing advanced string-matching algorithms.

Frequently Asked Interview Questions

Q1. Why does first + first work?

Every possible rotation of a string appears as a contiguous substring of the doubled string.

Example

ABCD

↓

ABCDABCD

Contains

BCDA

CDAB

DABC

ABCD

Q2. Which solution is best for interviews?

The Concatenation + contains() approach is usually the preferred answer because it is concise, easy to explain, and runs in linear time.

Mention KMP as an optimized alternative when interviewers ask about implementing substring search manually.

Q3. Why must the string lengths be equal?

A rotation only changes the starting position of characters.

It never adds or removes characters.

Therefore,

length(A)

=

length(B)

must always be true.

Q4. What is the difference between rotation and reversal?

Rotation

ABCDE

↓

CDEAB

Reversal

ABCDE

↓

EDCBA

Rotation preserves the cyclic order of characters, while reversal flips the entire sequence.

Q5. What is the complexity of the optimal solution?

Using concatenation followed by linear-time substring search (such as KMP), the solution runs in:

  • Time: O(n)
  • Space: O(n)

Interview Tip

If an interviewer asks:

"Check whether one string is a rotation of another."

Start with the Concatenation + contains() solution because it is the standard interview answer.

Then discuss more advanced approaches:

  1. Concatenation + contains() (most common)
  2. Manual Rotation (conceptual understanding)
  3. StringBuilder (mutable implementation)
  4. KMP (linear-time pattern matching)
  5. Rolling Hash / Rabin-Karp (advanced substring searching)

Finally, ask clarifying questions such as:

  • Are both strings guaranteed to have the same length?
  • Can I use built-in methods like contains()?
  • Should the solution be case-sensitive?
  • Is this a one-time comparison or part of a larger pattern-matching system?

Explaining the trade-offs between these approaches demonstrates strong problem-solving skills and a solid understanding of Java string algorithms.