WAP to find the index in an circular array such that the string that is formed starting from that index is first in lexicographic order.

For Ex : in the circular array ABCDEABCCDE
The answer is 6 because the circular string starting from the element A in the 6th position comes first in the dictionary formed from all the possible strings of the circular array

what is lexicographic order
Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as
(a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).

so basically we have to print 1st index from differentstring formed by same character leads different lexicographic order such that string comes 1st then other string in lexicographic order from all others .Some of you may stuck with language i written but example makes you more clear

so in case of Given string s= ABCDEABCCDEA
A comes at 0,5 & 11th position as you can see AA comes 1st then ABCCDE in lexicographic order or alphabetically order or dictionary order then ABCDE so output will be 11 not 0 or 5th index . you can easily visualize it you know about TRIE or Dictionary

This problem can be Solved in Two Ways

1st Simple Iterative Solution

#include
#include


int findIndex(const char* str){

int minindex= 0, i, j, k, temp, len = strlen(str);

for(i = 1; i < len; ++i){

if(str[i] < str[ret]){

minindex= i;

} else if(str[i] == str[ret]){

k = i;
temp= ret;

for(j = 0 ; j < len; j++){

k = (k + j) % len;
temp= (temp + j) % len;

if(str[k] < str[l]){
minindex = i;
break;//once we found minindex terminate to optimize the inner loop
}
}
}
}
return ret;
}
int main() {

char *s = "ABCDEABCCDEA";

printf("%d\n", findIndex(s));
}

Time Complexity O(N^2) when suppose ABCDEFGHACDEFGHA so only inner loop will run until last index of A. isn't it i suggest you to dry run it.
Space Complexity O(1)
Run Here http://ideone.com/rgMSE

2nd DP Solution

PS:Working On The Code ..