lexicographical strings

lexicographical
strings
#1

In few competitions i came across problems on Lexicographical Strings but i didn’t understand anything.

So what actually is a Lexicographical String and what is the meaning of minimum string rotation, also what approach is required to deal with these kind of problems ?

#2

It would not have been lexicographic string. It would have been a lexicographically SMALLER or lexicographically larger string. What it means is say i have a string ABCDE and i have another string ABCDF. Then the first string is lexicographically smaller than the 2nd one. Since E appears before F in the alphabetical order. Thus you can understand it as “a lexicographically smaller string appears before a larger one, if both are kept in a dictionary”. Thats the best of saying it.

#3

Alternatively you can use suffix array.

#4

hello @rishabhprsd7,

For lexicographical sorting we can also use strcmp function in c.

example:solution for Problem : link text

#5

Lexicographic order is an order in which words are displayed in alphabetical order using the appearance of letters in the word. It is also know as dictionary order or alphabetical order.For ex:-“Africa” is smaller than “Bangladesh” ,“He” is smaller than “he”.

for more info, refer this link Lexicographic order

#6

http://ww.w.hackerrank.com/contests/csindia14-qr2/challenges/largest-lexicographical-rotation

During Codesprint this was one of the question asked. Can you please tell me the approach to solve this problem.


Main Aim : Given a string, output it’s largest lexicographical rotation.



Sample Input:

3
bidhan
zorro
apple

Sample Output: 
nbidha
zorro
pplea

Please can you explain me the approach..
#7

Find all such possible strings. Print the largest :stuck_out_tongue: --> http://ideone.com/Mv7iRo :slight_smile:

#8

Thanks @kaushik_iiitd

But i dont know anything about stl and c++… can you please explain me this line

ans=max(ans,(s.substr(i,s.length())+s.substr(0,i)));
#9

Brother, you may use a code in C : http://ideone.com/cDUV3P
It’s easy, you’ll surely get it on your own.

#10

@topcoder_7 your code gives wrong answers. Example - For blowhowler, the output should be wlerblowho but your code gives whowlerblo. http://ideone.com/WBbOpb . Kaushik gave the correct code.

#11

@rishabhprsd7 that line is nothing. Its just an inbuilt function in stl class string. What that line does is that it adds up the substrings from position i to s.length() (which is the complete length of the string) and the string from position 0 to i. Example abcde and say i=2. Then this line will give you cde+ab= cdeab. Thus it is just rotating the string.

#12

Thanks brother for correcting the code. @pranjalranjan

#13

Thanks it was really helpful!! :slight_smile: