Minimum rotations required to get the same string
Last Updated :
25 Jul, 2022
Given a string, we need to find the minimum number of rotations required to get the same string.
Examples:
Input : s = "geeks"
Output : 5
Input : s = "aaaa"
Output : 1
The idea is based on below post.
A Program to check if strings are rotations of each other or not
- Step 1 : Initialize result = 0 (Here result is count of rotations)
- Step 2 : Take a temporary string equals to original string concatenated with itself.
- Step 3 : Now take the substring of temporary string of size same as original string starting from second character (or index 1).
- Step 4 : Increase the count.
- Step 5 : Check whether the substring becomes equal to original string. If yes, then break the loop. Else go to step 2 and repeat it from the next index.
Implementation:
C++
#include <iostream>
using namespace std;
int findRotations(string str)
{
string tmp = str + str;
int n = str.length();
for (int i = 1; i <= n; i++) {
string substring = tmp.substr(i, str.size());
if (str == substring)
return i;
}
return n;
}
int main()
{
string str = "abc";
cout << findRotations(str) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG
{
static int findRotations(String str)
{
String tmp = str + str;
int n = str.length();
for (int i = 1; i <= n; i++)
{
String substring = tmp.substring(
i, i+str.length());
if (str.equals(substring))
return i;
}
return n;
}
public static void main(String[] args)
{
String str = "aaaa";
System.out.println(findRotations(str));
}
}
|
Python3
def findRotations(str):
tmp = str + str
n = len(str)
for i in range(1, n + 1):
substring = tmp[i: i+n]
if (str == substring):
return i
return n
if __name__ == '__main__':
str = "abc"
print(findRotations(str))
|
C#
using System;
class GFG {
static int findRotations(String str)
{
String tmp = str + str;
int n = str.Length;
for (int i = 1; i <= n; i++)
{
String substring =
tmp.Substring(i, str.Length);
if (str == substring)
return i;
}
return n;
}
public static void Main()
{
String str = "abc";
Console.Write(findRotations(str));
}
}
|
PHP
<?php
function findRotations($str)
{
$tmp = ($str + $str);
$n = strlen($str);
for ( $i = 1; $i <= $n; $i++)
{
$substring = $tmp.substr($i,
strlen($str));
if ($str == $substring)
return $i;
}
return $n;
}
$str = "abc";
echo findRotations($str), "\n";
?>
|
Javascript
<script>
function findRotations( str) {
var tmp = str + str;
var n = str.length;
for (var i = 1; i <= n; i++) {
var substring = tmp.substring(i ,str.length);
if (str===(substring))
return i;
}
return n;
}
var str = "abc";
document.write(findRotations(str));
</script>
|
Time Complexity: O(n2)
Auxiliary Space : O(n)
We can 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 the right substring and left substring and check whether it is equal to original string
Implementation:
C++
#include <iostream>
using namespace std;
int findRotations(string str)
{
int ans = 0;
int n = str.length();
for(int i=1;i<n-1;i++)
{
if(str.substr(i,n-i) + str.substr(0,i) == str)
{
ans = i;
break;
}
}
if(ans == 0)
return n;
return ans;
}
int main()
{
string str = "abc";
cout << findRotations(str) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG
{
static int findRotations(String str)
{
int ans = 0;
int n = str.length();
for(int i=1;i<str.length()-1;i++)
{
if(str.substring(i, str.length()-i) + str.substring(0, i) == str)
{
ans = i;
break;
}
}
if(ans == 0)
return n;
return ans;
}
public static void main(String[] args)
{
String str = "abc";
System.out.println(findRotations(str));
}
}
|
Python3
def findRotations(Str):
ans = 0
n = len(Str)
for i in range(1 , len(Str) - 1):
if(Str[i: n] + Str[0: i] == Str):
ans = i
break
if(ans == 0):
return n
return ans
Str = "abc"
print(findRotations(Str))
|
C#
using System;
class GFG {
static int findRotations(String str)
{
int ans = 0;
int n = str.Length;
for(int i=1;i<str.Length-1;i++)
{
if(str.Substring(i,n-i) + str.Substring(0,i) == str)
{
ans = i;
break;
}
}
if(ans == 0)
return n;
return ans;
}
public static void Main()
{
String str = "abc";
Console.Write(findRotations(str));
}
}
|
Javascript
<script>
function findRotations(str)
{
let ans = 0;
let n = str.length;
for(let i = 1; i < str.length - 1; i++)
{
if(str.substr(i, n - i) + str.substr(0, i) == str)
{
ans = i;
break;
}
}
if(ans == 0)
return n;
return ans;
}
let str = "abc";
document.write(findRotations(str),"</br>");
</script>
|
Time Complexity: O(n2)
Auxiliary Space: O(1)
Alternate Implementation in Python :
C++
#include <iostream>
using namespace std;
int main()
{
string String = "aaaa";
string check = "";
for(int r = 1; r < String.length() + 1; r++)
{
check = String.substr(0, r) + String.substr(r, String.length()-r);
if(check == String){
cout<<r;
break;
}
}
return 0;
}
|
Java
import java.io.*;
class GFG {
public static void main (String[] args) {
String string = "aaaa";
String check = "";
for(int r = 1; r < string.length() + 1; r++)
{
check = string.substring(0, r) + string.substring(r, string.length());
if(check.equals(string)){
System.out.println(r);
break;
}
}
}
}
|
Python3
string = 'aaaa'
check = ''
for r in range(1, len(string)+1):
check = string[r:] + string[:r]
if check == string:
print(r)
break
|
C#
using System;
class GFG {
public static void Main()
{
String str = "aaaa";
String check = "";
for(int r = 1; r < str.Length + 1; r++)
{
check = str.Substring(0, r) + str.Substring(r, str.Length-r);
if(check == str){
Console.Write(r);
break;
}
}
}
}
|
Javascript
<script>
let string = 'aaaa'
let check = ''
for(let r=1;r<string.length+1;r++){
check = string.substring(r) + string.substring(0,r)
if(check == string){
document.write(r)
break
}
}
</script>
|
Time Complexity: O(n2), n as length of string
Auxiliary Space: O(n), n as length of string
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...