You are not logged in. Please login at www.codechef.com to post your questions!

×

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 ?

asked 30 Oct '14, 00:49

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11243
accept rate: 14%

edited 30 Oct '14, 01:44


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.

link

answered 30 Oct '14, 01:17

pranjalranjan's gravatar image

4★pranjalranjan
2.0k21432
accept rate: 20%

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

(30 Oct '14, 01:41) rishabhprsd72★
2

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

(30 Oct '14, 02:08) kaushik_iiitd2★

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

(30 Oct '14, 07:28) rishabhprsd72★

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

(30 Oct '14, 09:53) topcoder_72★
1

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

(30 Oct '14, 11:57) pranjalranjan4★
1

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

(30 Oct '14, 12:01) pranjalranjan4★

Thanks brother for correcting the code. @pranjalranjan

(30 Oct '14, 12:41) topcoder_72★
1

Thanks it was really helpful!! :)

(30 Oct '14, 13:44) rishabhprsd72★
showing 5 of 8 show all

Alternatively you can use suffix array.

link

answered 30 Oct '14, 09:44

japoorv's gravatar image

5★japoorv
29592356
accept rate: 0%

hello @rishabhprsd7,

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

example:solution for Problem : link text

link

answered 21 Aug '15, 23:49

deepakmourya's gravatar image

4★deepakmourya
1145
accept rate: 16%

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

link

answered 17 Nov '15, 12:10

satishdixit's gravatar image

0★satishdixit
11
accept rate: 0%

edited 17 Nov '15, 12:11

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×354
×28

question asked: 30 Oct '14, 00:49

question was seen: 23,524 times

last updated: 17 Nov '15, 12:11