## 题目 1467: [蓝桥杯][基础练习VIP]完美的代价

时间限制: 1Sec 内存限制: 128MB 提交: 1659 解决: 536

**题目描述**
```
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。

交换的定义是：交换两个相邻的字符

例如mamad

第一次交换  ad  :  mamda

第二次交换  md  :  madma

第三次交换  ma  :  madam  (回文！完美！)
```
**输入**
```
第一行是一个整数N，表示接下来的字符串的长度(N  < =  8000) 

第二行是一个字符串，长度为N.只包含小写字母 
输出
如果可能，输出最少的交换次数。 

否则输出Impossible 

```
**样例输入**
```
5 
mamad
```
**样例输出**
```
3
```

### 思路一


```
n=int(input())
l=list(input())

def find(target,l,n):
    i=n-1
    while i>=0:
        if target==l[i]:
            return i
        i-=1
def swap(i,j,l):
    if i<=j:
        temp=l[i]
        t=j-i
        for k in range(t):
            l[i+k]=l[i+k+1]
        l[j]=temp
    return l
k=0
res=0
label=0
while k<=(n//2-1):
    j=n-1-k
    if l[k]==l[j]:
        k+=1
    else:
        i=find(l[k],l[k:j+1],n-2*k)+k
        if i==k:
            if n%2==0:
                print('Impossible')
                label=1
                break
            else:
                l=swap(i,i+1,l)
                res+=1
        else:
            l=swap(i,j,l)
            res+=j-i
            k+=1

if label==0:
    print(res)   


```

    7847
    fdkzklcfzyuhivkbxnocsizsvkppdyuxaznbcxjmihvtrdpbepgjcffpkjwybhslljvwwvpzmvxxjozykikfwbrddjtbdebxvvttbnqaarmkvdvanbdhdchyilcmodoiiunqtikddvpmrkpiztampaagfukaslozztwsyteiiyksmwntlrxczldclgarwkaypxujkhtacmlnprmvkdvdbxsysoglpdrbmuhfceutkrxjhqrxfoaecdgdsalqrpxplvnctwamwaajfapqmezxikcyeegyocyiqiltmcdxpdfhjdbhnlivdwkygctihktsutwjplqhepzkrtolgtqmcmwvpbzlhvrwkztgtonhelqutjomhalxbrwzjqpsodzmjsalxvgxgdnutaseseqoysqzrgyetikmvzklphyfrrihugwnhuzidyaqpbodphhyjiecmryvtgyfsgnaxuvvtoamfuwrlzqkpevigdngbckrwvjvytebhmcvrovixxxtqalwliiapmwifezoperwwypwwghtuswkjvnotxegtqzpvfsauydgpklzotupvnhjcjyldjdgtbipzmnszkqpquvusvgdvfwptpzkisxkvhzposvvnxuhayphfplrdmouyvqmtvmrqxnwykrwxhnnnefmkituyttxeqhrjikemwqylveegrwlvlqdzdwuzjcmpveuscpbcnidfsxbluxxxaepjaqzsaiigzgpxiuyiognquvveszucyiuwpqesmhyfjorspusfvuqyenqlryragxnihdegqllgqoyfgwxaxegenleinvxkiftnkjiipdeqxlakjqufihkjxsupuvontntlsqiswrmovsipyulyqcsxnvjnaqttcblnkejdhjcibayfewgbiuekjlvdysnvolskbptfshwabpysqereamxtoydkrbswowuiyfwfvbfakkgtxnuqwmxwmatbnfchjaampuwmzcmoddmahtavzokckryrizzfxbobwnnzxvghcypcamxuhzbjynlzlkhzjdtgwbdajhxhajdxbedxkpqmbsfcaxtwsegabxvvadlerkbeqpyccrjewzkilrgyzdyiojjrsukewvtenrxzsdlpmbznmkbuotctowchgcwrwbqvfywdsebrjinhahgkasxbirdvilfdazgxlezknwjuhxkafntttljzzkubhgmtwqwokiatoqflpckkmkhfgrohhmalstdmyxuwnanhfbdgtrrsqxxqyctvnaykbzkirloozmhuvrvztdrvapcyubiwxnetdyzdbyihbhjqynumfdkwpzvcpupzouklvwsccgewnmorfiuqatnwmnaozdvzycpvxmrilgsykximfcitsnzsprzduxhwixagyfuecquctgzkopgaxmyvsfxyijfjjgzwhcdivrfmvtkubegkfbrynqxfvsvnzafclkfszwxlvcvikovwasqnixexilkpubsdsozccuoyxtpszkmsmuzmgttkkfhgsuaicsbhzpxzrneomnejqhkfmltwhkvmpefqzdtmadxgtscbdftrkjayulvhlpcprnxgryadrkwoarjgzuatkheuvtdtxiknsfqyuqhowbmnuysnamxenzauxgmlpaltffnaiadgqnpswecimeroavjdlryjtzgznhceqlengueuwdwegjxbjdspirxwegzzpuvujlugrlbfqmlifgsnedlsjrthcfedqpfzayviuigrgqjtqbcimxewmxnidjgjnqshubkwjilnhlaeeyysgxihknkdjoqtibhlfnkfsshgskxyptlnwyokvnruqrtkfliuaknhcmsqmaabvpskppbcwjtblwvfhyyquwkqnidonifgdtivsmcijpdxnsjytxtnmyxvzxrkkdqcusfgsrxwervarycsscpogymccfrjpctwdpcfkkfchiflzitbwazwurzryrmbyvsgnibmmldvrtjeywdydahixdntvfxxyqvhdsofxxbwqkggynybaaoqkyfafjipuqvexmshifjxjgznhpzwiytxkvofxidnfgvgnvpodpzvspntrrsdwhyhsucwjoenayigtmqiaxmlmamohmnrxjiomjvphxslfwrdmltvzrxnrvjlxuyubcwjulunfegfypwxcwpoduekwbjfhhwdijmymzhecummckwegggsjauahmocdwqzyzooylyutivttzebksukgmavbtsmlzujzdyeikabrqrixkismlxthotgkgaoxelhzqknmguwhuqzswalhprdbarubzsbsathyxpqrzihlkepgnnumbozxmbmagwjnvpiqhusbmemaivopofekcervnecptgqsyygxdaiqygvymbhralfqpyzbokmsmknxpibhekqmihvpgqxpmbktqiifcsugzldchfygpdysxmnhilvaaoarcwyxumrwotahailehxbyqgkkutflczojbzttwlgqbobizvsuzxiigzablwqxvvjvxenvuzfwlzijarcoywnuzejoihkerjoivvnaywpgvgmgcqfhexkonshgmgaemudywivlqghwswpjyvktdhnhigizzhiencsrehqvaznmvbvgzdesaeuetfykpmupvxcpbflhnipnhawxiikrrztznzewixwipfsmozbxyswsmymcpwckizzpbbyzamudnoxxhhfitrvzariqiltmhbpiostorafdxodmqseoiefzrmlxgbrniuuzexvhsbnybwrseygkogzghwoicblwsbdgcasydgxcxvptmtkixpwbdzfjhkeeevlqygdudcqxrivhejrctainfzjazvmfmelwulnaxbczealkqfiqwsfjhwprafxwmdrhbbourjpslwrjlhdsptzakqqcwsusgiozuuocftlsupxnetqhealgamhowyoabvacgjhezhrjpssmeyvhvslwzakahkeiloriihntexdphiurvcerwcwkftqwszmtmdwadjbcpxljduejbpazsgluoqnrcouomavbkxryzlvrhxmpstgdxbpsawipusnatocxsoqulkbxevqjbzwecymtydtjjypewmhhhmjpaihybuxiryuqgbjnyspammyzaefvlzmgvtqrvlvzhbxsesqbaghccfdtirwauvweymioyznrgpooqorcmwmzpkyfzgickjqtjwghwtpchudyscinfgjfkkzwlriopfhmjupnpktiakbkttwubfzrdfjdrqibfykggaraoqyswobpngmjjuywxrqpobckbpbtdzqdcgdyafkoflmjxhdljqvtvmdbiyoafmigwxhevfpxucnncwydaiqcnwjrgjxmckkuiaokysatipfylmvflaeqfhrgbhqdvinpbrfwyofmyggbicafcutzucqzxxlsoycvaklcubhbbxwzrhpodloejherwttletirwbsqvbexbvmoeucjogjamnczfaxatywoccklrlkiylgviqhnpqorhylkirlsuvdyqtbcgyqrxoiheicokbavpuwsahlankcggcrahqhvrilyphmtwlpwydfxzvahbbmmkmeigwrxcjomiabkacbxremziklosvbzivmqghrlvvnoarjyxgqsktjpqfvrgpelscokehfjqkrppiwjvygnohkzaqewkkicmplyxpboacgqzdlmtzkgslfcbfdjcrsgokqprdrvquyjpyubienziuldnkxcjciihyszzswkjojeegzgamuuzatubkvdjgurflccyxletmnpbwadsakhickjmvqovwrhmmkwrslbgxydazcpffysbavvieuqetcxipnksjahfzzkmnvahzxovgrcnbvtrdkppmevuscrwlkivmrckwmfsugpizyooqjmbnscraygtujpjjkisytxvqnqyuvqmbvsxdtlriwbrkcdjphgmfqbdisgckrvkxsjnaqeslahrjblequaukjqsbrpiziiqzpkuhjgerhdrirksbhhrvtklrnyykiomxqkpcelkphroqsuvkmivabfxpuahnpqzekwsnrkxqtzhyxfcqlkhudnqoplpcbcyfycmjrmrrbknmsgxckeedhwmmvyugkuqflmtdbhflaujjpnkteeuehxcduiknevguakcfdxubvbppygvanmjnjtmznxirgozwmatnebkseccjnnhoqqdezyygoncmbahbphczsdohgivbtcxdiiljcknizdrsicgrbsefpurbpxjtqnesuojdyvjujbxroxlsxszugihenfpsqlycnoworgrnyjzrknxwldsluuelfqdqsholeoocmvdauugrkdyawfugtmdtmmukvppjlonqidldwxbaeccoehzfyjdlwwzkucephrbahldykixpsskoayumirbxvfzouupznxkvcwdhmqqrfkjmjbyfhykrbirkhekuzlmimapqintpzvgnplovkkqkmzbtlcjiwtgqwvqhdsprxcsgawtovdrltjmyztxrtggcmrubdtltkvmgubsnrhaunvnawexaqytxxalpdconpjcmmeqrhdvwmviwjjizaqrvaftjvbskmtszgycqflgymeipkdsfguftmcbxspeorpnizxzrwszbatgyyygriwpjrpaqwcrykytihsmwaexuqqihxidqtyzalhkcwovezzjknnvhxeazehwoubvpivltgzphqisdlgkkqmegmuisyvjieakiproivnaeuynmjlxoypahxirmzvinpcxklhzhulktsnuhfinjnqozamcxgggjizvlimhupyywinbnockxtaxfmeukildeyqvfumnpdduujaaaxbdsatifqbqqtviimsmbyegsstkhcdtjtabdttbjvqynxzhnfelongxmofcenpnotfvnbmqyeeavqlmzqxnmgdikibxuwbuugtdikkxmcbhtgnlrzxmpskllrytywfveqbbbaauxyvljdyctkvngmkkvzzpnihsymwdlotwvxujmqaqskhabyjcdosdjgalqiplkvhxnazezjbwhymoincwnplbpsdadibmcyovihrpcmbhtwvceyxcousqikemnpioecwzbmmjdbxyaljsmkulvsvoozmujsloxlwsippcwlaoxdgjtyaiolkyniniiakpksqqziutheuqqblfiifccuxcqsxzqahfwyocvwlflwwiesqpkhleyfhjqsbmvwecuwdurnitvmrpohnmqbvmgcuutvdhqzcyibdzlzifxcxvgqtnevvtfktmmqpvvypliyesejxpivylunocnwufizulnwpqnmfavzgkufoxaierswyiiyzbolmqedcuihsywgcqkxaenaqljvrwnmuojckyifjwljzdzbzlgrjevgksaymfaaeahcrmibbszzoxgnwqfyfijrfurliizjtbijwgdskicqnmuhdzypxuvovzqchxrwihstgbviakungphxerhijjrhmhbdmsgwfyxjdhiaxkthgkatvlqegcovxilthhniboaqnwvizabxwlmhyaatqddfwdxfrsrzylimkaimqbikonagevxwiawjwywxziftbzxlxdezrldikqhyjdpyzqdlrrudcefjaswaohhvfasnkurcaxwoiurrgqzrxtrcfiuvitzoqpglmgbpmeekjbywcgzbrpglgujjhfrixloodpupuywaddmkrjkylxdanfjlpsuetrddqndqpfumfffxlzhttdklwktuwzktrmwtsfemhycbhhltyoiwlbroutrvtwktwghemivakwyzwgixvwhoqxuovxslkkhziievwwxafimdhtzccentfyyqbalinpxsryegitavfkgwvykhzcmtopovpzfezmllljqbwwgrvkjgywsisowhcgvsxwtgfvectfpodpptgsgvqwptprpmzdykyuzjxlnibmzzpjeawmgiamrvfqrgybvtlqxcwjmlcoaiflyllvluzzxtslaaxqexzdxdnvrcluspopxvxkycecmjlyfnvrwdwnkxnfmaqrlckuwzwgxkxsakqgfmgvhlwrtkustuwokizjksuogdqqwhyonkcwuquhidvaiepiravjjihbvlsujevpsawagecqvcollazzvthgxnrrozxorzjgjrqzblrfxzqndfavhjvaiftozcldlcxddtatatxndoboxlqcysmotxhxmcdtztgcvybdiusuebvuefozwzehnxzjbxjutwaabqxfuiomqznfysimtprihmbtajodsrntqvjgyubexnrhfgelhbrmexgwiuuuomxvamgadrrszdqghsntsfhsfgliuaqvemewxbsfcvmvviqejevkloomdbdjysawqpiorvzrhrgsnqoeamqnkttzynsrsfhkamdswmnfuytykrzkngcynlowepabfbfuptbyysafaeivimsksbwthkbfrxkhmvwspwyltjwmrsmdfmocsnszlacqheorueucwtwwthymjegpynwdumrztwpxhhsonodwszfzhqundwqdmqspfwwhgoodmgcwidgyzmjwjlostsxtrmukxcfsiudrmkmqigzpyiswiyveufyvvqufjxhalgdejwpmhswzchfbspkcoyrpttrxuwcebcjxogsqgesheujpcmeqfwpmrntkutsvpuwdsqpsxtwkzrwppmyatibvpgcvnjfyzlszyldesviqhetixjqisoclwrdmfxtwoddjegabhwnaexvpvpahvtkezjhxihnusccujsffzsansuiobrrezbtzpnhmzjwuszkpckejshhvyncwznklgklsmakmbkqwwcuejswasvtptlgnqzvyuftzvrldutawjyyhduwpliabwwpyxvqtrwuxvzgfubvpadpzppvnlzmqqtdekmzknmjglhgnpvifuvwrsbiudivzolvtqidhrklyyxcjhlsqcnxrbtikctwxmniknmlpttoormkwxmslrdpmucjxixnyfbaznzwtkhxhsiojwkdvgkmeeaoqatxtxtpbwllrwwgxnufvtjhmtkeaurmtqisniaiglxaerpxlkdwnqowkcpzycimnhxosoyfdadluuopqgwwmzshjfuiqwhtjaxeayhtlugvrclkfymjubuhsanfpwscyexyaxvxoxrurbsfrwxrliamdcwqqmivhafpxbvsvsopbprxfkrwaeatepgnvcxhmxbvjadmmnflmhmhypaznzptoewprirvxxciheutbttrxbhtcoyjlceidlylvrpzeitzkgnhopdgkdztjovsyntcxyjjcolcdpipoxnnbxdwppoyulptnblrarzvjosnximcsoobaioeitxxjlbnqsqvcxblwmuzynunoisylhaezvikfudtfdzilbmvrcwniphvauywdhytpvfbiqndwjowxfapauryferyixvvpnqnrclyxbwsljjeyszcnoaucyhunxkieghvmwhlhyhxowtmsfpuctpphkgxhsikqmehzivuqgzxsdysedxzkltdfqjdaadrvynpyhwaudezwvquinmpnkjvkwtlhkfkxiqllvtrxmjbrfbgvsuqihpwhwopmagizhuknlushnzgiknyublzpnajxcdchfkkodrgqfjlnjjeccdbbhfvalpwrckqntrankglwikiekqzfgweuukfriugiluwoeiwwjzgifmyuwzvyeqvovdynpfsmejzsttuvbtklzxynvauxsgbewrhrvipn
    460825


### 思路二


```



def main():
    def swap(point_left,point_right):
        temp=s[point_left]
        for i in range(point_left,point_right):
            s[i]=s[i+1]
        s[point_right]=temp
        return point_right-point_left
    
    
    n=int(input())
    s=list(input().strip())
#     print(s)
    i=0
    res=0
    while i<=(n//2-1):
        point_right=n-1-i
        if s[i]==s[point_right]:
            i+=1
        else:
            point_left=''.join(s[i:point_right+1]).rfind(s[i])+i
            if point_left==i:
                if n%2==0:
                    print('Impossible')
                    return 
                else:
                    res+=swap(point_left,point_left+1)
            else:
                res+=swap(point_left,point_right)
                i+=1
    print(res)
    return 
main()


```

    5
    mamad
    3