1. Overview
In our daily Java programming, strings are often the fundamental objects we must handle. Sometimes, we need to rotate a given string by n characters. Rotating a string involves shifting its characters in a circular manner, creating a dynamic and visually engaging effect.
In this tutorial, we’ll explore different ways to solve the string rotation problem.
2. Introduction to the Problem
When we say rotating a string by n characters, it means shifting n characters in the string. An example can help us understand the problem quickly.
2.1. An Example
Let’s say we have a string object:
String STRING = "abcdefg";
If we take STRING as the input, after rotating it n characters, the results will be the following:
- Forward Rotation -
Input String : abcdefg
Rotate (n = 1) -> gabcdef
Rotate (n = 2) -> fgabcde
Rotate (n = 3) -> efgabcd
Rotate (n = 4) -> defgabc
Rotate (n = 5) -> cdefgab
Rotate (n = 6) -> bcdefga
Rotate (n = 7) -> abcdefg
Rotate (n = 8) -> gabcdef
...
The example above illustrates the behavior of forward string rotation. However, the string can also be rotated in the opposite direction—backward rotation, as depicted below:
- Backward Rotation -
Input String : abcdefg
Rotate (n = 1) -> bcdefga
Rotate (n = 2) -> cdefgab
Rotate (n = 3) -> defgabc
Rotate (n = 4) -> efgabcd
Rotate (n = 5) -> fgabcde
Rotate (n = 6) -> gabcdef
Rotate (n = 7) -> abcdefg
...
In this tutorial, we’ll explore both forward and backward rotations. Our objective is to create a method capable of rotating an input string in a specified direction by shifting n characters.
To keep things simple, we’ll limit our method to accepting only non-negative values for n.
2.2. Analyzing the Problem
Before we dive into the code, let’s analyze this problem and summarize its key characteristics.
First, if we rotate the string by shifting zero (n=0) characters, irrespective of the direction, the result should mirror the input string. This is inherently clear since no rotation occurs when n equals 0.
Furthermore, if we look at the example, when n=7, the output equals the input again:
Input String : abcdefg
...
Rotate (n = 7) -> abcdefg
...
This phenomenon arises because the length of the input string is 7. When n equals STRING.length, each character returns to its original position after the rotation. Consequently, the result of rotating STRING by shifting STRING.length characters is identical to the original STRING.
Now, it becomes evident that when n = STRING.length × K (where K is an integer), the input and output strings are equal. In simpler terms, the effective n’ to shift characters is essentially n % STRING.length.
Next, let’s look at the rotation directions. Upon comparing the forward and backward rotation examples provided earlier, it shows that *“backward rotation with n” is essentially equivalent to “forward rotation with STRING.length – n“*. For instance, a backward rotation with n=2 yields the same result as a forward rotation with n=5 (STRING.length – 2), as illustrated below:
- Forward Rotation -
Rotate (n = 5) -> cdefgab
...
- Backward Rotation -
Rotate (n = 2) -> cdefgab
...
So, we can only focus on solving the forward rotation problem and transform all backward rotations into forward ones.
Let’s briefly list what we’ve learned so far:
- The effective n’ = n % STRING.length
- n=0 or K × STRING.length: result = STRING
- “Backward rotation with n” can be transformed into “Forward rotation with (STRING.length – n)”
2.3. Preparing the Testing Data
As we’ll use unit tests to verify our solutions, let’s create some expected output to cover various scenarios:
// forward
String EXPECT_1X = "gabcdef";
String EXPECT_2X = "fgabcde";
String EXPECT_3X = "efgabcd";
String EXPECT_6X = "bcdefga";
String EXPECT_7X = "abcdefg"; // len = 7
String EXPECT_24X = "efgabcd"; //24 = 3 x 7(len) + 3
// backward
String B_EXPECT_1X = "bcdefga";
String B_EXPECT_2X = "cdefgab";
String B_EXPECT_3X = "defgabc";
String B_EXPECT_6X = "gabcdef";
String B_EXPECT_7X = "abcdefg";
String B_EXPECT_24X = "defgabc";
Next, let’s move to the first solution, “split and combine”.
3. Split and Combine
The idea to solve the problem is to split the input string into two substrings, then exchange their position and recombine them. As usual, an example will help us to quickly understand the idea.
Let’s say we want to forward rotate STRING by shifting two (n=2) characters. Then, we can perform the rotation in the following way:
Index 0 1 2 3 4 5 6
STRING a b c d e f g
Sub1 [a b c d e] -->
Sub2 <-- [f g]
Result [f g] [a b c d e]
Therefore, the key to solving the problem is finding the index ranges of the two substrings. This isn’t a challenge for us:
- Sub 1 – [0, STRING.length – n), In this example, it’s [0,5)
- Sub 2 – [STRING.length – n, STRING.length) In this example, it’s [5, 7)
It’s worth noting that the half-open notation “[a, b)*” employed above indicates that the index ‘*a*‘ is inclusive, while ‘*b*‘ is exclusive. Interestingly, **Java’s String.subString(beginIndex, endIndex) method coincidentally follows the same convention of excluding the endIndex*, simplifying index calculations.
Now, building upon our understanding, the implementation becomes straightforward:
String rotateString1(String s, int c, boolean forward) {
if (c < 0) {
throw new IllegalArgumentException("Rotation character count cannot be negative!");
}
int len = s.length();
int n = c % len;
if (n == 0) {
return s;
}
n = forward ? n : len - n;
return s.substring(len - n, len) + s.substring(0, len - n);
}
As observed, the boolean variable forward indicates the direction of the intended rotation. Subsequently, we employ the expression “n = forward ? n : len – n” to seamlessly convert backward rotations into their forward counterparts.
Furthermore, the method successfully passes our prepared test cases:
// forward
assertEquals(EXPECT_1X, rotateString1(STRING, 1, true));
assertEquals(EXPECT_2X, rotateString1(STRING, 2, true));
assertEquals(EXPECT_3X, rotateString1(STRING, 3, true));
assertEquals(EXPECT_6X, rotateString1(STRING, 6, true));
assertEquals(EXPECT_7X, rotateString1(STRING, 7, true));
assertEquals(EXPECT_24X, rotateString1(STRING, 24, true));
// backward
assertEquals(B_EXPECT_1X, rotateString1(STRING, 1, false));
assertEquals(B_EXPECT_2X, rotateString1(STRING, 2, false));
assertEquals(B_EXPECT_3X, rotateString1(STRING, 3, false));
assertEquals(B_EXPECT_6X, rotateString1(STRING, 6, false));
assertEquals(B_EXPECT_7X, rotateString1(STRING, 7, false));
assertEquals(B_EXPECT_24X, rotateString1(STRING, 24, false));
4. Selfjoin and Extract
The essence of this approach lies in concatenating the string with itself, creating SS = STRING + STRING. Consequently, regardless of how we rotate the original STRING, the resulting string must be a substring of SS. Hence, we can efficiently locate the substring within SS and extract it.
For instance, if we forward rotate STRING with n=2, the result is SS.subString(5,12):
Index 0 1 2 3 4 5 6 | 7 8 9 10 11 12 13
SS a b c d e f g | a b c d e f g
|
Result a b c d e [f g a b c d e] f g
Now, the problem transforms into identifying the expected start and end indexes in the self-joined string SS. This task is relatively straightforward for us:
- Start index: STRING.length – n
- End index: StartIndex + STRING.length = 2 × STRING.length – n
Next, let’s “translate” this idea into Java code:
String rotateString2(String s, int c, boolean forward) {
if (c < 0) {
throw new IllegalArgumentException("Rotation character count cannot be negative!");
}
int len = s.length();
int n = c % len;
if (n == 0) {
return s;
}
String ss = s + s;
n = forward ? n : len - n;
return ss.substring(len - n, 2 * len - n);
}
This method passes our tests too:
// forward
assertEquals(EXPECT_1X, rotateString2(STRING, 1, true));
assertEquals(EXPECT_2X, rotateString2(STRING, 2, true));
assertEquals(EXPECT_3X, rotateString2(STRING, 3, true));
assertEquals(EXPECT_6X, rotateString2(STRING, 6, true));
assertEquals(EXPECT_7X, rotateString2(STRING, 7, true));
assertEquals(EXPECT_24X, rotateString2(STRING, 24, true));
// backward
assertEquals(B_EXPECT_1X, rotateString2(STRING, 1, false));
assertEquals(B_EXPECT_2X, rotateString2(STRING, 2, false));
assertEquals(B_EXPECT_3X, rotateString2(STRING, 3, false));
assertEquals(B_EXPECT_6X, rotateString2(STRING, 6, false));
assertEquals(B_EXPECT_7X, rotateString2(STRING, 7, false));
assertEquals(B_EXPECT_24X, rotateString2(STRING, 24, false));
So, it solves our string rotation problem.
We have learned STRING‘s rotation result will be a substring of SS. It’s worth noting that we can use this rule to check if a string is rotated from the other string:
boolean rotatedFrom(String rotated, String rotateFrom) {
return rotateFrom.length() == rotated.length() && (rotateFrom + rotateFrom).contains(rotated);
}
Finally, let’s test the method quickly:
assertTrue(rotatedFrom(EXPECT_7X, STRING));
assertTrue(rotatedFrom(B_EXPECT_3X, STRING));
assertFalse(rotatedFrom("abcefgd", STRING));
5. Conclusion
In this article, we first analyzed the rotating a string by n characters problem. Then, we explored two different approaches to solving this problem.
As always, the complete source code for the examples is available over on GitHub.