How to Check if a String is a Rotation of Another in Go

Checking if one string is a rotation of another is a common programming challenge. In this blog, we will explore an efficient way to solve this problem using Go. The method we use is simple and runs in O(n) time, making it ideal for real-world applications and coding interviews.

What is String Rotation? A string rotation means that a string can be derived from another string by shifting its characters while maintaining their order. For example:

• "waterbottle" rotated can result in "erbottlewat".
• "rotation" rotated can become "tationro".
• "abcdef" rotated can become "defabc".
• "golang" rotated can become "langgo".
• "developer" rotated can become "operdevel".

To check if one string is a rotation of another, we use a clever trick:

• Concatenate the original string with itself.
• Check if the second string appears as a substring in the concatenated version.

Go Implementation

Here’s an optimized implementation in Go:

package main

import (
	"fmt"
	"strings"
)

func isRotation(s1, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}
	return strings.Contains(s1+s1, s2)
}

func main() {
	fmt.Println(isRotation("rotation", "tationro"))       // Output: true
	fmt.Println(isRotation("hello", "world"))            // Output: false
}

Explanation of the Code

1. Check Lengths: If the lengths of s1 and s2 are different, return false immediately.
2. Concatenation: We concatenate s1 with itself to ensure all possible rotations are included.
3. Substring Check: We use strings.Contains to check if s2 appears within the concatenated string.

Time Complexity Analysis

The solution runs in O(n) time:

• Concatenation takes O(n).
• Checking for substring presence using strings.Contains takes O(n) in the worst case.

Edge Cases Considered

• If s1 and s2 have different lengths, return false.
• If s1 and s2 are identical, return true.
• Works correctly even if s1 contains special characters or spaces.
• If s1 is empty, it should return false.

FAQs

Q1: What is the best approach to check string rotations in Go?
A: The best approach is to concatenate s1 with itself and check if s2 is a substring of it using strings.Contains.

Q2: Does this approach work for all edge cases?
A: Yes, it works for different lengths, identical strings, and even special characters.

Q3: Can this method be used in large-scale applications?
A: Yes, it runs in O(n) time, making it efficient for large inputs.

Conclusion Checking if one string is a rotation of another can be efficiently solved using a simple trick with string concatenation. This method is widely used in interviews and real-world applications due to its optimal performance. With an O(n) complexity, it ensures efficiency and accuracy in detecting rotated strings.