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



Sample input:
3
aababb


Sample output:
abab

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def search_ab(sss, cursor):
    # print('a', 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):
    # print('b', 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))
repeat_a = 0
parts_b = []
cursor = 0
while cursor < n2:
    c = sss[cursor]
    if c < 0:
        repeat, cursor = search_ab(sss, cursor)
        repeat_a += repeat
    else:
        tmp, cursor = search_ba(sss, cursor)
        parts_b.append(tmp)
if parts_b:
    print(integrate(parts_b))
else:
    print('ab' * repeat_a)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def search_ab(sss, cursor):
    # print('a', 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:
            tmp_cur = max_cur
            break
        ai = aaa.index(cur)
        tmp_cur = bbb[ai]
        repeat += 1
    return repeat, tmp_cur + 1


def search_ba(sss, cursor):
    # print('b', cursor)
    first_bi = bbb.index(cursor)
    last_cursor = sss.index(0, cursor)
    last_bi = aaa.index(last_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, last_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))
repeat_a = 0
parts_b = []
cursor = 0
while cursor < n2:
    c = sss[cursor]
    if c < 0:
        repeat, cursor = search_ab(sss, cursor)
        repeat_a += repeat
    else:
        tmp, cursor = search_ba(sss, cursor)
        parts_b.append(tmp)
if parts_b:
    print(integrate(parts_b))
else:
    print('ab' * repeat_a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

ab_index = {'a': 0, 'b': 0}
ab_dic = {}
i = 0
while i < (2 * n):
    ab_dic[i] = (s[i], ab_index[s[i]])
    ab_index[s[i]] += 1
    i += 1

import copy


class Info:
    def __init__(self, string, includeds, excludeds):
        self.string = string
        self.includeds = includeds
        self.excludeds = excludeds

    def include(self, s, i):
        dic = copy.copy(self.includeds)
        dic[(s, i)] = True
        return Info(self.string + s, dic, self.excludeds)

    def exclude(self, s, i):
        dic = copy.copy(self.excludeds)
        dic[(s, i)] = True
        return Info(self.string, self.includeds, dic)

    def __repr__(self):
        return '({0}, {1}, {2})'.format(self.string, self.includeds, self.excludeds)



dp = [[None for _ in range(len(s) + 1)] for _ in range(len(s) + 1)]
dp[0][0] = Info('', {}, {})


for i in range(len(s)):
    ab, abi = ab_dic[i]
    for j in range(i + 1):
        inf = dp[i][j]
        if inf is None:
            continue
        if inf.string == 'aa':
            dp[i][j] = None
            continue

        if ab == 'a':
            if inf.includeds.get(('b', abi)):
                dp[i + 1][j + 1] = inf.include('a', abi)
            elif inf.excludeds.get(('b', abi)):
                candidate = inf.exclude('a', abi)

                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string <= candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
            else:
                dp[i + 1][j + 1] = inf.include('a', abi)

                candidate = inf.exclude('a', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string <= candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
        if ab == 'b':
            if inf.includeds.get(('a', abi)):
                dp[i + 1][j + 1] = inf.include('b', abi)
            elif inf.excludeds.get(('a', abi)):
                candidate = inf.exclude('b', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string < candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
            else:
                dp[i + 1][j + 1] = inf.include('b', abi)

                candidate = inf.exclude('b', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string < candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass


print(sorted(map(lambda x: x.string, filter(lambda x: x is not None, dp[-1])))[-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

ab_index = {'a': 0, 'b': 0}
ab_dic = {}
i = 0
while i < (2 * n):
    ab_dic[i] = (s[i], ab_index[s[i]])
    ab_index[s[i]] += 1
    i += 1

import copy


class Info:
    def __init__(self, string, includeds, excludeds):
        self.string = string
        self.includeds = includeds
        self.excludeds = excludeds

    def include(self, s, i):
        dic = copy.copy(self.includeds)
        dic[(s, i)] = True
        return Info(self.string + s, dic, self.excludeds)

    def exclude(self, s, i):
        dic = copy.copy(self.excludeds)
        dic[(s, i)] = True
        return Info(self.string, self.includeds, dic)

    def __repr__(self):
        return '({0}, {1}, {2})'.format(self.string, self.includeds, self.excludeds)



dp = [[None for _ in range(len(s) + 1)] for _ in range(len(s) + 1)]
dp[0][0] = Info('', {}, {})


for i in range(len(s)):
    ab, abi = ab_dic[i]
    for j in range(i + 1):
        inf = dp[i][j]
        if inf is None:
            continue

        if ab == 'a':
            if inf.includeds.get(('b', abi)):
                dp[i + 1][j + 1] = inf.include('a', abi)
            elif inf.excludeds.get(('b', abi)):
                candidate = inf.exclude('a', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string <= candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
            else:
                dp[i + 1][j + 1] = inf.include('a', abi)

                candidate = inf.exclude('a', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string <= candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
        if ab == 'b':
            if inf.includeds.get(('a', abi)):
                dp[i + 1][j + 1] = inf.include('b', abi)
            elif inf.excludeds.get(('a', abi)):
                candidate = inf.exclude('b', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string < candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
            else:
                dp[i + 1][j + 1] = inf.include('b', abi)

                candidate = inf.exclude('b', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string < candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass

print(sorted(map(lambda x: x.string, filter(lambda x: x is not None, dp[-1])))[-1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
idx=[[0,0]for _ in[0]*N]
a=b=0
for k,x in enumerate(input()):
    if x=='a':
        idx[a][0]=k
        a+=1
    else:
        idx[b][1]=k
        b+=1
res=[]
for i in range(1,2**N):
    tmp=[0]*2*N
    for k in range(N):
        if (i>>k)&1:
            a,b=idx[k]
            tmp[a]='a'
            tmp[b]='b'
    res+=[''.join(c for c in tmp if c)]
print(max(res))

Submission status: Accepted

Solution code:
from itertools import accumulate


def search_ab(sss, cursor):
    # print('a', 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):
    # print('b', 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))

Submission status: Runtime Error

Solution code:
import bisect
from itertools import accumulate, combinations


def search_ab(sss, cursor):
    ai = aaa.index(cursor)
    tmp_cur = bbb[ai]
    repeat = 1
    while sss[tmp_cur] < 0:
        repeat += 1
        ai = bisect.bisect(aaa, tmp_cur, lo=ai)
        if ai >= n:
            tmp_cur = n2 - 1
            break
        tmp_cur = bbb[ai]
    return 'ab' * repeat, tmp_cur + 1


def search_ba(sss, cursor):
    first_bi = bbb.index(cursor)
    last_cursor = sss.index(0, cursor)
    last_bi = aaa.index(last_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, last_cursor + 1


def integrate(parts_a, parts_b):
    if not parts_b:
        return ''.join(parts_a)
    tmp_max = ''
    for k in range(1, len(parts_b) + 1):
        for cmb in combinations(parts_b, k):
            tmp = ''.join(cmb)
            if tmp > tmp_max:
                tmp_max = tmp
    return tmp_max


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

# n = 10
# s = ['a', 'b'] * n
# import random
#
# random.seed(4)
# random.shuffle(s)
# s = ''.join(s)
# print(s)

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))
parts_a = []
parts_b = []
cursor = 0
while cursor < n2:
    c = sss[cursor]
    if c < 0:
        tmp, cursor = search_ab(sss, cursor)
        parts_a.append(tmp)
    else:
        tmp, cursor = search_ba(sss, cursor)
        parts_b.append(tmp)
print(integrate(parts_a, parts_b))

Submission status: Runtime Error

Solution code:
import bisect
from itertools import accumulate, combinations


def search_ab(sss, cursor):
    ai = aaa.index(cursor)
    tmp_cur = bbb[ai]
    repeat = 1
    while sss[tmp_cur] < 0:
        repeat += 1
        ai = bisect.bisect(aaa, tmp_cur, lo=ai)
        tmp_cur = bbb[ai]
    return 'ab' * repeat, tmp_cur + 1


def search_ba(sss, cursor):
    first_bi = bbb.index(cursor)
    last_cursor = sss.index(0, cursor)
    last_bi = aaa.index(last_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, last_cursor + 1


def integrate(parts_a, parts_b):
    if not parts_b:
        return ''.join(parts_a)
    tmp_max = ''
    for k in range(1, len(parts_b) + 1):
        for cmb in combinations(parts_b, k):
            tmp = ''.join(cmb)
            if tmp > tmp_max:
                tmp_max = tmp
    return tmp_max


n = int(input())
n2 = n * 2
s = input()
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))
parts_a = []
parts_b = []
cursor = 0
while cursor < n2:
    c = sss[cursor]
    if c < 0:
        tmp, cursor = search_ab(sss, cursor)
        parts_a.append(tmp)
    else:
        tmp, cursor = search_ba(sss, cursor)
        parts_b.append(tmp)
print(integrate(parts_a, parts_b))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()

ab_index = {'a': 0, 'b': 0}
ab_dic = {}
i = 0
while i < (2 * n):
    ab_dic[i] = (s[i], ab_index[s[i]])
    ab_index[s[i]] += 1
    i += 1

import copy


class Info:
    def __init__(self, string, includeds, excludeds):
        self.string = string
        self.includeds = includeds
        self.excludeds = excludeds

    def include(self, s, i):
        dic = copy.copy(self.includeds)
        dic[(s, i)] = True
        return Info(self.string + s, dic, self.excludeds)

    def exclude(self, s, i):
        dic = copy.copy(self.excludeds)
        dic[(s, i)] = True
        return Info(self.string, self.includeds, dic)

    def __repr__(self):
        return '({0}, {1}, {2})'.format(self.string, self.includeds, self.excludeds)



dp: [[Info]] = [[None for _ in range(len(s) + 1)] for _ in range(len(s) + 1)]
dp[0][0] = Info('', {}, {})


for i in range(len(s)):
    ab, abi = ab_dic[i]
    for j in range(i + 1):
        inf = dp[i][j]
        if inf is None:
            continue

        if ab == 'a':
            if inf.includeds.get(('b', abi)):
                dp[i + 1][j + 1] = inf.include('a', abi)
            elif inf.excludeds.get(('b', abi)):
                candidate = inf.exclude('a', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string <= candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
            else:
                dp[i + 1][j + 1] = inf.include('a', abi)

                candidate = inf.exclude('a', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string <= candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
        if ab == 'b':
            if inf.includeds.get(('a', abi)):
                dp[i + 1][j + 1] = inf.include('b', abi)
            elif inf.excludeds.get(('a', abi)):
                candidate = inf.exclude('b', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string < candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass
            else:
                dp[i + 1][j + 1] = inf.include('b', abi)

                candidate = inf.exclude('b', abi)
                if dp[i + 1][j] is None:
                    dp[i + 1][j] = candidate
                else:
                    if dp[i + 1][j].string < candidate.string:
                        dp[i + 1][j] = candidate
                    else:
                        pass

print(sorted(map(lambda x: x.string, filter(lambda x: x is not None, dp[-1])))[-1])