# Python Solution with comments beating 90%

• 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)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.