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 = "geeks";
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)
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 = "geeks"
Output: 5
Explanation:
i=1 : substring ="eekgeeks"
i=2 : substring ="ekgeeks"
i=3 : substring ="kgeeks"
i=4 : substring ="kgee"
i=5 : substring ="geeks"
Example 2:
Input: str = "abc"
Output: 3