This code seems not so clean, but it is easy to understand.
All invalid password is due to three problem: length, repeat, char_miss
We first find all these three problem in the string and solve it one by one.
Main idea about this solution is that, we solve
repeat problem together with
def strongPasswordChecker(self, s): """ There are mainly three kinds of problem: 1. length problem: 6 <= len(s) <= 20 if too long, can be solved by delete if too short, can be solved by insert 2. repeat problem: '...aaaaaa...' is illegal can be solved by delete, insert and replace 3. other problem: uppercase, lowercase, digit can be solved by insert and replace """ # init the problem start, end = 0, 0 length_change = 0 if len(s) < 6: length_change = 6 - len(s) if len(s) > 20: length_change = len(s) - 20 lower_flag = 1 upper_flag = 1 digit_flag = 1 repeats =  # find the repeating parts while end < len(s): while end < len(s) and s[start] == s[end]: if s[end].isdigit(): digit_flag = 0 elif s[end].isupper(): upper_flag = 0 elif s[end].islower(): lower_flag = 0 end += 1 if end - start >= 3: repeats.append(end-start) start = end repeats.sort() # number of `other problem` other_change = lower_flag + upper_flag + digit_flag # first handle problem could be solved by DELETE length_repeat = 0 if len(s) > 20: # an delete operation could solve both `lenght problem` and `repeat problem` while repeats and length_change: # it is the same to delete whether in the middle or in the begining # once apply an delete, the length of one repeating part decreased by one length_repeat += 1 # make one delete, count increment by 1 repeats -= 1 # repeats part decrement by 1 length_change -= 1 # solve one `length problem` if repeats < 3: repeats.pop(0) # if length of repeating part is less than 3, this part is totally solved if len(s) < 6: # an insert operation could slove both `length problem` and `repeat problem` while repeats and length_change: # we insert a new string into the repeating part every 2 character # e.g. for "aaaaa", we make it "aabaaa" for the first insertion, then "aabaaba" # Meanwhile, every insertion could solve one `other problem` length_repeat += 1 # make one insert, count increment by 1 repeats -= 2 # repeats part decrement by 2 length_change -= 1 # solve one `length problem` if other_change > 0: # solve one `other problem` other_change -= 1 if repeats < 3: # if length of repeating part is less than 3, this part is totally solved repeats.pop(0) # till now, we are sure that we have solved at least one of `repeat problem` or `length problem` # if there is still `repeat problem` left, count it and solve it with replace operation repeat_left = 0 for repeat in repeats: repeat_left += repeat / 3 # what left is length_repeat(fixed), other_change(replace/ins), length_change(ins/del) or repeat_left(replace) if len(s) > 20: # length_change could only be solved by deletion if length_change: return length_repeat + other_change + length_change else: return length_repeat + max(other_change, repeat_left) else: # length_change could be solved by ins if length_change: return length_repeat + max(other_change, length_change) else: return length_repeat + max(other_change, repeat_left)