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 `length problem`

```
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[0] -= 1 # repeats part decrement by 1
length_change -= 1 # solve one `length problem`
if repeats[0] < 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[0] -= 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[0] < 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)
```