You try to sort a list of 1000 elements - made up of only 16 distinct values - using Bubble Sort.
Unfortunately, the list is not given directly to you but rather you have a string of length 1000
consisting of letters 'a' to 'p', and you don't know which letter represents which number.
What's the highest number of Bubble Sort swaps that you might require?
Two elements a[i] and a[i+1] shall only be swapped if a[i] > a[i+1].
For example, the maximum number of swaps when given the (shorter) string 'abc' is 3
(for instance when a=3, b=2 and c=1).
Input: A string s of length 1000 consisting only of letters 'a' to 'p' (broken into segments of length up
to 80).
Answer: The maximum number of Bubble Sort swaps required to sort the represented list when choosing the
numerical values behind 'a' to 'p' in the most unfortunate way.
Example:
input:
joafbpdinkkccjebgbckfomfgdlflojknokpbnbonmafmjnhdejhncibedglhhhehjhhgmfadenldgbh
enddfincbcogaahfaokkbapgpnhihpfkfjdhaahdajnaojlaockmbpfkhlciodbgcbjkfhfjmhnjnfbk
ejlhmibenecllhhdhmgchhnlhgacajoedhgbjabjjpicfimnbhhcbhchgebcicjpdhkooahgcgnnmpmk
jclkckaahlooagdacencdfojfkffapfgkicghljojocjihpmkopfihckhhhiahnimdhpcohpphadgbfd
dfbihheefnokplhacnfkaanmfimahgijadcelgofempjckigglbbpokjgknjainfeliajioalpboloan
pgbgjlkdeddmobeodjngmblepleojmjacbjocfcgeadeeaffoppliebhjefendbnhbmjlgacaokipdbe
dghjkldlhoniipabcealnlkfacahlfljakpfjkelojajefhijhidephmcffohgejloeacnomakookmla
aajhgllcnfhmcmceljolmeknlkbicicpakgdjnfpocidngdlchalfhpmambgbkdcidcploocbjkkffmj
golnejbcbdkgcicdpfgnbinidhddkdgacegpjojopjedcklkddhiiiemkgnlnlcikilhehhgodaekgkc
bbiehlikmmfmidipkpnmhhenlojiaebahnaihaikinaldaabbokefhmoihakgbcnepmdkbhbonndejja
fgenhihnidjpmkoiljhlfkcgoohpklmckfdklghekgbkbkhnkmmkajjdiogkiocnbijkgmmbjnckgmba
lopokdpjgcihdpajlpolaiaknfnpjjmglkjoikcbbkdjmkhgfdknlbnhccdmabljoecncoljihbbhldp
hbhnicdkidnpcalfpombcnkaingmgjckajdnlbie
answer:
257571