String Rotations
LEVEL:Beginner
Description
A rotation on a string is defined as removing first element and concatenating it at the end
Given N and an array of N strings
Output the minimum no. of rotations on the strings so as to make all the strings equal.
If this is not possible return -1
Input Format
first line contains a string n
next n lines contain 1 string in each line.
Output Format
Single number denoting the no. of rotations
4 11234 34112 41123 11234
3
5 12345 23415 43251 31254 53124
-1
3 212 221 213
-1
Login to see Discussion
Approach
If there are no strings provided, return -1.
Else, create a dictionary/hashmap in which key is the string and value as the number of rotations it took to get into that form with respect to first string.
For each string from the second one onwards, if the lenght of the string is not equal to that of the first string, return -1.
Else, check for all possible rotations of a string if it is equal to any of the strings in the hashmap. If so, increase it's value by the number of rotations it took. Simply, it is equal to the current iteration of the loop.
As a final step, return the string from hashmap with the minimum value.
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution