lexicographical strings

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 Likes

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.

7 Likes

Alternatively you can use suffix array.

1 Like

hello @rishabhprsd7,

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

example:solution for Problem : link text

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

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…

Find all such possible strings. Print the largest :stuck_out_tongue:Mv7iRo - Online C++ Compiler & Debugging Tool - Ideone.com :slight_smile:

2 Likes

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)));

Brother, you may use a code in C : cDUV3P - Online C Compiler & Debugging Tool - Ideone.com
It’s easy, you’ll surely get it on your own.

@topcoder_7 your code gives wrong answers. Example - For blowhowler, the output should be wlerblowho but your code gives whowlerblo. WBbOpb - Online C Compiler & Debugging Tool - Ideone.com . Kaushik gave the correct code.

1 Like

@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.

1 Like

Thanks brother for correcting the code. @pranjalranjan

Thanks it was really helpful!! :slight_smile:

1 Like