linteanm
BAN USERMy previous solution was a miss, and maybe a bit complicated. But I really like Krutin's idea to iterate backwards on the input. So here is the implementation of that solution in python. Let me know if this works or not. Thanks.
s = 'cbacdcbc'
seen = dict()
a = list(s)
for i in reversed(range(len(a))):
if a[i] in seen:
if a[i+1] < a[i]:
a[i] = ''
else:
a[seen[a[i]]] = ''
seen[a[i]] = i
else:
seen[a[i]] = i
print ''.join(a)
Here is a Python version with complexity O(min(n, m)), where n is the length of first list, and m is the length of second list.
a = [2, 5, 5, 5]
b = [2, 2, 3, 5, 5, 7]
ia = 0
ib = 0
output = []
while ia < len(a) and ib < len(b):
if a[ia] < b[ib]:
ia += 1
elif a[ia] > b[ib]:
ib += 1
else: # they are equal
output.append(a[ia])
ia += 1
ib += 1
print output
The solution becomes more apparent after analyzing the input a bit. Based only on the first and last character, there are 4 types of strings: RR (starts in R, ends in R), RB (starts in R, ends in B), BR and BB.
We can combine all RRs into one big RR string, and all BBs into one big BB string. Both these big strings can be combined with any BR or RB string. If the input does not have any BR or RB strings then we return the size of the longest big string. It the input has at least one BR or RB, then we add the size of both big strings to our solution.
Now we reduced the problem into finding a solution when the input only has strings of type RB or BR. We gradually add to our solution the size of the longest strings, oscillating between the two classes. When we ran out of strings in one class, we can add one more string from the other class (if there is one) and then we are done.
The complexity in worst case scenario is n*log(n), due to sorting. Below is a Python implementation of the algorithm. Any feedback is most welcome.
strings = ['RRRR', 'BBB', 'R', 'BBB', 'RBBBB', 'RRB', 'BRBR', 'RBBB', 'BR']
RR = 0
BB = 0
RB = []
BR = []
for s in strings:
if s[0] + s[-1] == 'BB':
BB += len(s)
elif s[0] + s[-1] == 'RR':
RR += len(s)
elif s[0] == 'R': # and s[-1] = 'B'
RB.append(len(s))
else:
BR.append(len(s))
if not BR and not RB:
solution = max(RR, BB)
else:
RB.sort(reverse=True)
BR.sort(reverse=True)
solution = BB + RR
for i in range(min(len(BR), len(RB))):
solution += BR[i] + RB[i]
if len(RB) < len(BR):
solution += BR[len(RB)]
elif len(BR) < len(RB):
solution += RB[len(BR)]
print solution
- linteanm December 17, 2015