CSES Solutions – Minimal Rotation
A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.
Your task is to determine the lexicographically minimal rotation of a string.
Examples:
Input: s = “acab”
Output: abac
Explanation: All possible rotations are: “acab”, “caba”, “abac” and “baca”. The lexicographically smallest string is “abac”.Input: s = “w3wiki”
Output: BeginnerBeginnerfor
Explanation: Out of possible rotations “BeginnerBeginnerfor” is lexicographically smallest.
Approach: To solve the problem, follow the below idea:
The idea is to uses Booth’s algorithm, which is a well-known algorithm for this problem. The main idea of Booth’s algorithm is to construct a failure function (similar to the one used in the KMP pattern matching algorithm) for the given string concatenated with itself. This failure function is used to efficiently compare prefixes of the string to find the smallest rotation.
Let’s break our idea in some steps:
- Concatenate the string to itself: This allows us to easily handle the wrap-around nature of rotations without having to use modular arithmetic.
- Initialize the failure function and the minimum rotation index: The failure function f is an array that stores the length of the longest proper suffix of the substring S[0..j] which is also a proper prefix of S. The minimum rotation index k keeps track of the starting index of the smallest rotation found so far.
- Iterate over the concatenated string: For each character S[j] in the string, we compare it with the character at the corresponding position in the current smallest rotation. If S[j] is smaller, we update the minimum rotation index k.
- Update the failure function: The failure function is updated based on whether S[j] is equal to S[k + f[j – k – 1] + 1] . If they are equal, f[j – k] is set to f[j – k – 1] + 1. Otherwise, f[j – k] is set to -1.
- Return the minimum rotation index: After iterating over the entire string, the minimum rotation index k gives the starting index of the lexicographically smallest rotation.
Step-by-step algorithm:
- Create a function findMinRotation() takes a string s as input and finds the lexicographically minimal rotation of the string.
- It concatenates the input string with itself to avoid modular arithmetic.
- Create a failure function vector with -1 values and sets the initial minimum rotation index to 0.
- Iterates over the concatenated string to find the lexicographically minimal rotation.
- Updates the failure function and minimum rotation index based on comparisons.
- Returns the index of the lexicographically minimal rotation.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
// Function to find the lexicographically minimal rotation
// of a string
int findMinRotation(string s)
{
// Concatenate string to itself to avoid modular
// arithmetic
s += s;
// Initialize failure function
vector<int> failureFunc(s.size(), -1);
// Initialize least rotation of string found so far
int minRotationIdx = 0;
// Iterate over the concatenated string
for (int currentIdx = 1; currentIdx < s.size();
++currentIdx) {
char currentChar = s[currentIdx];
int failureIdx
= failureFunc[currentIdx - minRotationIdx - 1];
// Find the failure function value
while (
failureIdx != -1
&& currentChar
!= s[minRotationIdx + failureIdx + 1]) {
if (currentChar
< s[minRotationIdx + failureIdx + 1]) {
minRotationIdx
= currentIdx - failureIdx - 1;
}
failureIdx = failureFunc[failureIdx];
}
// Update the failure function and the minimum
// rotation index
if (currentChar
!= s[minRotationIdx + failureIdx + 1]) {
if (currentChar < s[minRotationIdx]) {
minRotationIdx = currentIdx;
}
failureFunc[currentIdx - minRotationIdx] = -1;
}
else {
failureFunc[currentIdx - minRotationIdx]
= failureIdx + 1;
}
}
// Return the index of the lexicographically minimal
// rotation
return minRotationIdx;
}
int main()
{
// input string
string s = "acab";
// Find the lexicographically minimal rotation
int minRotationIdx = findMinRotation(s);
// Print the lexicographically minimal rotation
cout << s.substr(minRotationIdx)
+ s.substr(0, minRotationIdx)
<< endl;
return 0;
}
import java.util.Arrays;
public class Main {
// Function to find the lexicographically minimal rotation of a string
static int findMinRotation(String s) {
// Concatenate string to itself to avoid modular arithmetic
s += s;
// Initialize failure function
int[] failureFunc = new int[s.length()];
Arrays.fill(failureFunc, -1);
// Initialize least rotation of string found so far
int minRotationIdx = 0;
// Iterate over the concatenated string
for (int currentIdx = 1; currentIdx < s.length(); ++currentIdx) {
char currentChar = s.charAt(currentIdx);
int failureIdx = failureFunc[currentIdx - minRotationIdx - 1];
// Find the failure function value
while (failureIdx != -1 && currentChar != s.charAt(minRotationIdx + failureIdx + 1)) {
if (currentChar < s.charAt(minRotationIdx + failureIdx + 1)) {
minRotationIdx = currentIdx - failureIdx - 1;
}
failureIdx = failureFunc[failureIdx];
}
// Update the failure function and the minimum rotation index
if (currentChar != s.charAt(minRotationIdx + failureIdx + 1)) {
if (currentChar < s.charAt(minRotationIdx)) {
minRotationIdx = currentIdx;
}
failureFunc[currentIdx - minRotationIdx] = -1;
} else {
failureFunc[currentIdx - minRotationIdx] = failureIdx + 1;
}
}
// Return the index of the lexicographically minimal rotation
return minRotationIdx;
}
public static void main(String[] args) {
// Input string
String s = "acab";
// Find the lexicographically minimal rotation
int minRotationIdx = findMinRotation(s);
// Print the lexicographically minimal rotation
System.out.println(s.substring(minRotationIdx) + s.substring(0, minRotationIdx));
}
}
// This code is contributed by shivamgupta310570
def find_min_rotation(s):
# Concatenate string to itself to avoid modular arithmetic
s += s
# Initialize failure function
failure_func = [-1] * len(s)
# Initialize least rotation of string found so far
min_rotation_idx = 0
# Iterate over the concatenated string
for current_idx in range(1, len(s)):
current_char = s[current_idx]
failure_idx = failure_func[current_idx - min_rotation_idx - 1]
# Find the failure function value
while (failure_idx != -1 and
current_char != s[min_rotation_idx + failure_idx + 1]):
if current_char < s[min_rotation_idx + failure_idx + 1]:
min_rotation_idx = current_idx - failure_idx - 1
failure_idx = failure_func[failure_idx]
# Update the failure function and the minimum rotation index
if current_char != s[min_rotation_idx + failure_idx + 1]:
if current_char < s[min_rotation_idx]:
min_rotation_idx = current_idx
failure_func[current_idx - min_rotation_idx] = -1
else:
failure_func[current_idx - min_rotation_idx] = failure_idx + 1
# Return the index of the lexicographically minimal rotation
return min_rotation_idx
def main():
# Input string
s = "acab"
# Find the lexicographically minimal rotation
min_rotation_idx = find_min_rotation(s)
# Print the lexicographically minimal rotation
print(s[min_rotation_idx:] + s[:min_rotation_idx])
if __name__ == "__main__":
main()
// Function to find the lexicographically minimal rotation
// of a string
function findMinRotation(s) {
// Concatenate string to itself to avoid modular
// arithmetic
s += s;
// Initialize failure function
const failureFunc = new Array(s.length).fill(-1);
// Initialize least rotation of string found so far
let minRotationIdx = 0;
// Iterate over the concatenated string
for (let currentIdx = 1; currentIdx < s.length; ++currentIdx) {
const currentChar = s.charAt(currentIdx);
let failureIdx = failureFunc[currentIdx - minRotationIdx - 1];
// Find the failure function value
while (failureIdx !== -1 && currentChar !== s.charAt(minRotationIdx + failureIdx + 1)) {
if (currentChar < s.charAt(minRotationIdx + failureIdx + 1)) {
minRotationIdx = currentIdx - failureIdx - 1;
}
failureIdx = failureFunc[failureIdx];
}
// Update the failure function and the minimum
// rotation index
if (currentChar !== s.charAt(minRotationIdx + failureIdx + 1)) {
if (currentChar < s.charAt(minRotationIdx)) {
minRotationIdx = currentIdx;
}
failureFunc[currentIdx - minRotationIdx] = -1;
} else {
failureFunc[currentIdx - minRotationIdx] = failureIdx + 1;
}
}
// Return the index of the lexicographically minimal
// rotation
return minRotationIdx;
}
// Main function
function main() {
// input string
const s = "acab";
// Find the lexicographically minimal rotation
const minRotationIdx = findMinRotation(s);
// Print the lexicographically minimal rotation
console.log(s.substring(minRotationIdx) + s.substring(0, minRotationIdx));
}
// Call the main function to execute the program
main();
Output
abac
Time Complexity: O(n), where n is the length of the input string s.
Auxiliary Space: O(n), where n is the length of the input string s.
Contact Us