JavaScript Program to Find Minimum Rotations Required to get the Same String
In this article, we are given a string str, our task is to find the minimum number of rotations required to get the same string using JavaScript.
Example 1:
Input: str = "Beginner"
Output: 5
Explanation:
i=1 : substring ="eekBeginner"
i=2 : substring ="ekBeginner"
i=3 : substring ="kBeginner"
i=4 : substring ="kgee"
i=5 : substring ="Beginner"
Example 2:
Input: str = "abc"
Output: 3
Approach 1: Evaluating Substrings after Concatenating string with itself (with auxiliary space)
- Create a string ‘temp’ which will contain the original string concatenated with itself.
- Iterate over the temp string using a for loop and for every iteration perform the below-mentioned steps.
- Take the substring of the ‘temp’ string of the same size as that of the original string starting from the second character which is at index 1.
- Check whether the substring which we just calculated becomes equal to the original string. If yes, then break the loop and return the value of i. Else repeat the steps from the next index.
- If no substring is equal to the original string in any iteration then we need to return the size of original string.
Example: This example shows the implementation of the above appraoch.
function minRotations(str) {
let temp = str + str;
let n = str.length;
for (let i = 1; i <= n; i++) {
// Use i + n to get the correct substring
let substr = temp.substring(i, i + n);
if (str === substr) {
return i;
}
}
return n;
}
let str = "Beginner";
console.log(
"Minimum Number of Rotations Required are:", minRotations(str));
let str2 = "zzzz";
console.log(
"Minimum Number of Rotations Required are:", minRotations(str2));
Output
Minimum Number of Rotations Required are: 5 Minimum Number of Rotations Required are: 1
Time Complexity: O(n2)
Auxiliary Space: O(n)
Approach 2: Partitioning & Concatenating both Left and Right substring (without auxiliary space)
In the previous approach, we were using an auxiliary variable ‘temp’ which was increasing our space complexity but we can also solve this problem without using any temporary variable as extra space. We will traverse the original string and at each position we partition it and concatenate both the left substring and the right substring and then check whether it is equal to original string. If yes, then return the value of res and break the loop but if res remains 0 then we have to return the size of original string.
Example: This example shows the implementation of the above appraoch.
function minRotations(str) {
let res = 0;
let n = str.length;
for (let i = 1; i < n; i++) {
if (str.substring(i) + str.substring(0, i) === str) {
res = i;
break;
}
}
if (res === 0)
return n;
return res;
}
let str = "Beginner";
console.log(
"Minimum Number of Rotations Required are:", minRotations(str));
let str2 = "aaa";
console.log(
"Minimum Number of Rotations Required are:", minRotations(str2));
Output
Minimum Number of Rotations Required are: 5 Minimum Number of Rotations Required are: 1
Time Complexity: O(n2)
Auxiliary Space: O(1)
Using Regular Expressions
Using regular expressions, the input string is concatenated with itself. A regex pattern is created to match the repeated string. The matched length of the repeated substring determines the minimum rotations needed to get the same string.
Example: In this example the function minRotationsUsingRegExp calculates the minimum number of rotations needed to return to the original string using regex.
function minRotationsUsingRegExp(s) {
let pattern = new RegExp('^(' + s + ')+$');
let rotatedStr = s + s;
let match = rotatedStr.match(pattern);
return match ? match[1].length : -1;
}
let str = "Beginner";
console.log("Minimum Number of Rotations Required are:"+minRotationsUsingRegExp(str));
Output
Minimum Number of Rotations Required are:5