I wrote code for task, but get error: time-limit-exceeded from testing system. I need to get advice how I can write this code faster and more precise
Code:
# input
n = int(input())
seq = input()
pairs = []
seq = list(seq)
# find pairs
counted = []
for i, item in enumerate(seq):
for j, num in enumerate(seq):
if (i != j) and (item == num):
if (i not in counted) and (j not in counted):
pairs.append((item, num))
counted.append(i)
counted.append(j)
# remove pairs from seq
for pair in pairs:
seq.remove(pair[0])
seq.remove(pair[1])
# create a palindrome
start = []
end = []
pairs = sorted(pairs)
pairs = list(reversed(pairs))
for item in pairs:
start.append(item[0])
end.append(item[1])
end = list(reversed(end))
if len(seq) != 0:
seq = [int(item) for item in seq]
max_el = list(sorted(seq))[-1]
start.append(max_el)
final_s = start end
# output
output = ''.join([str(item) for item in final_s])
print(output)
CodePudding user response:
It's an interesting problem and not completely trivial. First, I think the input can only have odd count of a single digit, otherwise it cannot be formed into a palindrome. For example, 11333 is a valid input, but 113334 is not (both 3 and 4 have odd counts). It should also be noted that we cannot just dump the odd-count digits in the middle of the output. For example, we might be tempted to do 1335551 -> 3155513, but the correct answer (largest palindrome) is 5315135.
Given these constraints, here's my attempt at a solution. It uses collections.Counter
to count the digit pairs, which are then sorted in descending order and mirrored to create the output. The possible odd-count digit is handled by treating it as a single digit (which goes into the middle of the output), plus a bunch of paired digits.
I tested it for input sizes of 10^5 digits and it didn't seem to take much time at all.
from collections import Counter
def biggest_pal(n):
c = Counter(str(n))
s = ''
evens = {k: v for k, v in c.items() if not v % 2}
odds = {k: v for k, v in c.items() if v % 2}
vodd = ''
if len(odds) > 1:
raise ValueError('Invalid input')
elif odds:
vodd, nodd = odds.popitem()
if nodd > 1:
evens[vodd] = nodd - 1
for k, v in sorted(evens.items(), key=lambda p: -int(p[0])):
s = k * int(v/2)
return s vodd s[::-1]
Some test inputs:
biggest_pal(112) # 121
biggest_pal(1122) # 2112
biggest_pal(1234123) # 3214123
biggest_pal(1331555) # 5315135
biggest_pal(112212) # ValueError: invalid input