Exact the same idea, similar time (~40ms):

def nextClosestTime(self, time):
isV = lambda t: t[:2] < '24' and t[3:] < '60'
can = sorted(set(time))[:-1]
for i in (4, 3, 1, 0):
for n in can[can.index(time[i])+1:]:
ntime = (time[:i] + n).ljust(5, can[0])
if isV(ntime):
return ntime[:2] + ':' + ntime[3:]
else:
break
return can[0]*2 + ':' + can[0]*2

Update, another one, still the same idea with slightly different tricks on dealing corner cases (also ~40ms).

def nextClosestTime(self, time):
pos = sorted(set(time))[:-1]
nxt = dict(zip(pos, pos[1:] + ['']))
isV = lambda t: t[:2] < '24' and t[3:] < '60'
for i in (4, 3, 1, 0):
n = nxt[time[i]]
res = (time[:i] + n).ljust(5, pos[0])
if n and isV(res): break
else:
res = pos[0] * 5
return res[:2] + ':' + res[3:]

But I have to say both are ugly as hell