Problem:
 Score : 1600 points    Problem Statement You are given a string S of length 2N , containing N occurrences of a and N occurrences of b .  You will choose some of the characters in S . Here, for each i = 1,2,...,N , it is not allowed to choose exactly one of the following two: the i -th occurrence of a and the i -th occurrence of b . (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order).  Find the lexicographically largest string that can be obtained in this way.      Constraints  1 \leq N \leq 3000  S is a string of length 2N containing N occurrences of a and N occurrences of b .         Input Input is given from Standard Input in the following format:  N  S       Output Print the lexicographically largest string that satisfies the condition.        Sample Input 1 3
aababb      Sample Output 1 abab  A subsequence of T obtained from taking the first, third, fourth and sixth characters in S , satisfies the condition.       Sample Input 2 3
bbabaa      Sample Output 2 bbabaa  You can choose all the characters.       Sample Input 3 6
bbbaabbabaaa      Sample Output 3 bbbabaaa       Sample Input 4 9
abbbaababaababbaba      Sample Output 4 bbaababababa

Solution (Python):
from itertools import accumulate


def search_ab(sss, cursor):
    
    ai = aaa.index(cursor)
    tmp_cur = bbb[ai]
    max_cur = sss.index(0, cursor)
    repeat = 1
    while tmp_cur < max_cur:
        cur = s.find('a', tmp_cur, max_cur)
        if cur == -1:
            break
        ai = aaa.index(cur, ai)
        tmp_cur = bbb[ai]
        repeat += 1
    return repeat, max_cur + 1


def search_ba(sss, cursor):
    
    first_bi = bbb.index(cursor)
    max_cursor = sss.index(0, cursor)
    last_bi = aaa.index(max_cursor)

    tmp_buf = [''] * (last_bi - first_bi + 1) * 2
    tmp_max = ''
    for i in range(last_bi, first_bi - 1, -1):
        tmp_buf[aaa[i] - cursor] = 'a'
        tmp_buf[bbb[i] - cursor] = 'b'
        tmp = ''.join(tmp_buf)
        if tmp > tmp_max:
            tmp_max = tmp
    return tmp_max, max_cursor + 1


def integrate(parts_b):
    tmp_max = ''
    for pb in reversed(parts_b):
        tmp = pb + tmp_max
        if tmp > tmp_max:
            tmp_max = tmp
    return tmp_max


n = int(input())
s = input()

n2 = n * 2
sss = []
aaa, bbb = [], []
for i, c in enumerate(s):
    if c == 'a':
        aaa.append(i)
        sss.append(-1)
    else:
        bbb.append(i)
        sss.append(1)
sss = list(accumulate(sss))
repeats_a = []
parts_b = []
last_b_cur = 0
cursor = 0
while cursor < n2:
    c = sss[cursor]
    if c < 0:
        repeat, cursor = search_ab(sss, cursor)
        repeats_a.append((cursor, repeat))
    else:
        tmp, cursor = search_ba(sss, cursor)
        parts_b.append(tmp)
        last_b_cur = cursor
print(integrate(parts_b) + 'ab' * sum(r for c, r in repeats_a if c > last_b_cur))