Problem Statement
Librarians prefer mental exertion to manual labor. When a librarian confronts a disordered shelf of books, he restores it to order using the smallest possible number of moves. With each move, he takes out a book and reinserts it so that neighboring books slide right and left as necessary.
You are given a
Definition
- Class:
- Books
- Method:
- sortMoves
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int sortMoves(String[] titles)
- (be sure your method is public)
Notes
- The standard string comparators of C++, Java, C#, and VB.Net perform case-sensitive lexical comparison.
- Do not strip any blank character from any title.
Constraints
- titles contains between 1 and 20 elements, inclusive.
- Each element of titles will contain between 1 and 50 characters, inclusive.
- Each character of each element of titles will be a letter ('a'-'z' or 'A'-'Z') or a space (' ').
Examples
{"Algorithms", "Purely Functional Data Structures", "Intro to C", "Automata and Computability"}
Returns: 2
We can sort these books by first removing "Intro to C" and placing it at the end of the shelf, and then by removing "Purely Functional Data Structures" and placing it at the end.
{"the fellowship of the ring", "the return of the king", "The two towers"}
Returns: 1
Remember that uppercase letters sort before lowercase ones in this problem.
{"Basic Engineering Circuit Analysis", "A Course in Combinatorics", "Artificial Intelligence", "Asimovs Guide to Shakespeare", "The Nature of Space and Time", "A Time for Trumpets", "Essentials of Artificial Intelligence", "Life by the Numbers", "Cognitive Psychology", "ColdFusion"}
Returns: 5
I could sort this section of my bookshelf in only 5 moves, but computer scientists are even lazier than librarians.
{"A", "B", "A", "A", "B"}
Returns: 1
Observe that there are three copies of the "A" book, and two of the "B" book. Since the three "A" books are indistinguishable, we can sort these books by simply removing the first of the two "B" books and then putting it at the end.
{"BNBURPJQBE","YUQSYFXKJV","NMLBUBRXZX","SSCNSNSNWS","GWGFPSJBBC","HNYWQSPBKL","CKUPYOHTRC","EVPVEMXOYZ","FMPTJWXXMQ"}
Returns: 5
{"BKWYYNGLYL","HTETBIEKZM","USWXLDDPJY","ZLDKXSATZY"}
Returns: 0
{"SQWYMIZZFH","UFQPRDDSBI","SJOUQEWGRO","WLPEQHTGLD","QBZFWXXKJQ","LQROYGRAWY","ONENMYHGGA","PMMBUFQPIG","XJNQGNUITI","SXUMISPBAQ","CMBKZUQZTA","HFDOOXGENI","BJUSUTVVCN"}
Returns: 9
{"BWQZQIGTAL","RAKVMRGOPV"}
Returns: 0
{"BPPBYEHBFN","RSROUBCWHF","HIXZNHCSSA","ANVFOTVEMD","WTTCVWDDDX","CUKAQBNTDT","FRSRTSPLIR","RBLHHAOLQG","LLXYXNGSNL","ZOZVYOVJKJ","YFNRUZLYLZ","ZAOFPYFLOG","JDJEJKNMFT","ZDJAIBTBIR","RIJJGYJWBY"}
Returns: 8
{"GWAQTXABON","OESCEENPAP","MMYKIRPCVI","LDMNLQFEBU","QJRHIGWQYX","CQBINXUVRG","IHYZUODVZG","MHWPUZPYGQ","CXGYDCSCGO"}
Returns: 6
{"ZVFSOIOPEP","LVQXNFBBCM","OXOBQITDLI","URVVKXTKKN","IVANZBVQLK","YEXSQIOXAS","JSKPXXPFAD"}
Returns: 3
{"ASVSJWIVNX","ZZSKFJXGTP","NCQZTIRQJK","UZXANECZVY","VAEICNHQLV","LBKPVVIFIW","NPDBQCFFNE"}
Returns: 3
{"YKDZCFWCBH"}
Returns: 0
{"KCGTIJRAJL","ODOQEJJACR","BYDHTSFGSX","IPGHQOARPJ","QCJBZOHFVO","QWPZJOHIIG","GSTCBKCGLE","UHCTRSGZBT","OZLRKVGAZW","EWEINOGMNB","BQTTOWLUGP","JKQLVQCLJU","SNVQARUSPA","MMMOPCROLR","HGSIJFIXZA"}
Returns: 10
{"HRQUMUJJRY","TJBNIUWZVG","OBSSOIEHPY","ERDZEZXIER","TFOLBGEDPQ","TQXJVXMKTI","EKVUKAHELJ","YDIXKDRRYH","IYYTPDHBXZ","SLAYLJXRAT","FAQSIZSZMH","CVEKQXEYKH","JEYYQIENVJ","PKCYYGHOFN","ZUIAREKMCW","KIJWCVLNWI","NGIUPHTSXO","QINGENHYAD"}
Returns: 12
{"JGWKCTZXAT","JFLIDPRNDH","UODEHIJXBU"}
Returns: 1
{"NSKBYIZLQP","BTFZLZFGYW","NLIWKAJOKO","XVXMFGENWD","AIGRGAHSXT","ZYGNIGEBPJ","SWEKWEWRAY","ZGAORAXBXU","BXAOVVPXNG"}
Returns: 5
{"PEUQRLJZBJ","ZRHVGWIUXK","CYLSUSINHH","CXXXWVFQKL","NLBPIXMWYB","QVARLOVXQT","DYHLGNFWMH","SZPEVKYUIZ","FYHRSSTUUH","KVBYUYAKYX","IVXBIWQQNR","QSMPHPKXNK","OPVGTIDWWV","LAPLRVLVEZ","YTYJSITACG","GUCZZJVLKY","LNWOLHJPVN","ZAYAKAXWBM"}
Returns: 11
{"OUSKAZTPXQ","DIKGZRHZXZ","SYWICILKIW","IKKRIPROBW","QEDWZRFBUW","JUCCWSLRPO","WFAHUOSAEV"}
Returns: 3
{"XPIUDZLZFU","IJYRCUVGBO","QMETLSLQYB","YVOLQMQUQY","RXNHEABHHK","ZLFCQHQHAG","WDRLGMARKS"}
Returns: 3
{"XTHUBBFHJU","DTIFKWZLEK","TYZWHPGSTQ","GVRPMVIKZX","FEHBCDCGLN","JDITHIOMZS","ATLTOJUUDE","NWTLFBZMHF","HGWNNMKXRB"}
Returns: 5
{"QGKNMTGJBK","HHOYUMFALG","SOZLRPCVXP","NEFVTVQGAX","AKUOUZHOMB","XRRYZHHWAO","TBRFTYLSNM","XAGXWEVHEL","FANYLXMPLA","CHGDJJPBFK","ZYICCLGPBP","VLQRJOPGNF","VYPFLMHQVN","BZCWDXMZLT","FEUJFZOMDY","APUIWVNKOF","RUFAMJGAWL"}
Returns: 12
{"QGVQQAWDHA","HQUUPUJIWG","ZELKKLVDTY","GFSKBRYLLP","VVNTYJREKW","WBCQGUNAIM","GAAJOIXHNN","VBMEDJXAWT","LKTNFPJAJL","ZXUNDXPFPS","LEGZLWDXNF"}
Returns: 7
{"PGKMQKRTRR","OLSHXHKIXC","AJNROFCNBI","WFLPGKAPGM","VEUHUNIORF","ZKESEJLGDK","XEAPIPUMKF","HTLFIAJIZK","SQKWIIHYPQ","EGNDNIPBRF","SCBURQLZFS","ACCLZWNBNA","ZKTEPRLPTT","KKCTDJJJXJ","OBCUCTSZYM"}
Returns: 11
{"JKNISVGRCY","FAQKPISUDD","BYUJZBZCPM"}
Returns: 2
{"ONYEELBKFC"}
Returns: 0
{"KHOSFHDPNY","YYFXLOWEFC","LJPKHOLKDH","LDLMPXWLXQ","EEVAQNUXYQ","DOHDABSNVE","STDBWEEDBD","EHCALWMAVD","JLGRXDWRIU","GZZYLOQXXY","LFDUJVSSBT","KXNBHHFANX","WRDBWBHVGY","PWXFSZRMDC"}
Returns: 9
{"RIICZNMNYJ","RIIHQUZGEE","GQLOYDQZLU","XLJKZQRNHI","XBYKUDZGGX","AXRRRTCPWK","AQJYOUZKPS","MRPDUEWWIG","OOCTQSWCJU","PHUDKMGUGB","FJISWTTGLV","PMLNBIWWXT","ABGVEAMTPO","BPIHSZJSMQ"}
Returns: 9
{"TYEWQKITWG","YVZYITGFMU","JBEBHMJGAF","BJQAXWTVDM","XVCUGGQWGK","WFKJFLLAKN","YZANJRUCQJ","XAMVAIVJXN","MVPBOIDAIV"}
Returns: 6
{"PCABZEWBSP","ZFXECXPBYO","VUIZEWURYW","JOSAJAREWY"}
Returns: 2
{"KMOUOYOZCJ","GDBNLEECPK","OGHVEHLYZM","YEJBEOJXOP","ENSVYGFWGH","RYMKTEUSIH","WXYMNAFQUT","PDPTZAFTBI","WCSAHNITWP","XENRUVJWLD","CEIDZBXBWL","QIZSZYMVHJ","EDPEFRSHZA","KTQOLYDBEK","OWVKPYKWIR"}
Returns: 10
{"SGZPIANEYW","NYWVIQAKYU","AEMEEDIZET","TMWBANEDRP","FOGQVSMUVI","MSIJRDJHLJ","UXHSZZYLVJ","LOKAZHNJUC","ZGCFAPLOCQ","IXURLTJDSU","GVYZEIBJJV","GCXLDWBHXQ"}
Returns: 7
{"AVLKETSJHK","PJOUMPFXSK","IGEMJHFMDH","EGTPCWGEUK","MKZXFGMJVY","HWRVVBVJOA","OTMBZWDCJY","ZFOMQZNZTX","MPJROXPUDQ","YRYHEEKXMM","YTDEUYOUYU","HYABFWYCEK","JNOFWNBEES","WGQXQTVVCC","PWPTRYPOSA","VIFDNQNLUZ"}
Returns: 9
{"This Book Has No Title", " This Book Does Have A Title"}
Returns: 1
The blank character in the title affects its lexical order.
{"What Is The", "What Is The ", "What Is The Title Of This Book"}
Returns: 0
These books are already in order.
{"z","y","x","w","v","u","t","s","r","q","p","o","n","m","l","k","j","i","h","g"}
Returns: 19
{ "the fellowship of the ring", "the return of the king", "The two towers" }
Returns: 1
{ "Basic Engineering Circuit Analysis", "A Course in Combinatorics", "Artificial Intelligence", "Asimovs Guide to Shakespeare", "The Nature of Space and Time", "A Time for Trumpets", "Essentials of Artificial Intelligence", "Life by the Numbers", "Cognitive Psychology", "ColdFusion" }
Returns: 5
{ "A", "B", "A", "A", "B" }
Returns: 1
{ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAT", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAS", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAR", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQ", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAP", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAO", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAN", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAM", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAL", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAK", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAJ", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAI", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAH", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAG", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAF", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAE", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" }
Returns: 19
{ "Basic Engineering Circuit Analysis", "A Course in Combinatorics", "Artificial Intelligence", "Asimovs Guide to Shakespeare", "The Nature of Space and Time", "A Time for Trumpets", "Essentials of Artificial Intelligence", "Life by the Numbers", "Cognitive Psychology", "ColdFusion", "ColdFusion", "A Course in Combinatorics", "A Course in Combinatorics" }
Returns: 7
{ "z", "a", "b", "c", "d", "e" }
Returns: 1
{ "C", "B", "A", "D" }
Returns: 2
{ "z", "a", "b", "c", "d" }
Returns: 1
{ "A", "B", "C", "D", "E", "A", "B", "C", "D", "E", "A", "B", "C", "D", "E", "A", "B", "C", "D", "E" }
Returns: 12
{ "Z", "Y", "X", "W", "V", "U", "T", "Q", "N", "M", "L", "K", "J", "I", "H", "G", "F", "D", "C", "E" }
Returns: 18
{ "Z", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "A" }
Returns: 2
{ "Basic Engineering Circuit Analysis", "A Course in Combinatorics", "Artificial Intelligence", "Asimovs Guide to Shakespeare", "The Nature of Space and Time", "A Time for Trumpets", "Essentials of Artificial Intelligence", "Life by the Numbers", "Cognitive Psychology", "ColdFusion", "Crognitive Psychology", "asdf", "dfghf", "eartyrt", "re", "hr", "hrt", "h", "d", "rteryetyertyey" }
Returns: 8
{ "D", "C", "B", "A" }
Returns: 3
{ "T", "S", "R", "Q", "P", "O", "N", "M", "L", "K", "J", "I", "H", "G", "F", "E", "D", "C", "B", "A" }
Returns: 19
{ "B", "C", "A", "D" }
Returns: 1
{ "B", "C", "D", "A", "E" }
Returns: 1
{ "A", "B", "C", "D", "E", "S", "R", "Q", "L", "M", "N", "O", "P", "K", "J", "I", "H", "G", "F" }
Returns: 9
{ "D", "D", "C", "A", "A" }
Returns: 3