420. Strong Password Checker

• 420. Strong Password Checker
  • Description
  • Explanation
  • Solution
  • Reference

Description

Here

Explanation

Observation:

1. aaa -> del 1 or replace 1
2. aaaa -> del 2 or replace 1
3. aaaaa -> del 3 or replace 1

Therefore, generally we should use more replace to reduce the steps

Denote the input s

1. If len(s) < 6, we have to add 6 - len(s)
2. If 6 <= len(s) && len(s) <= 20, we only replace the right characters
3. If len(s) > 20, we have to delete len(s) - 20 any way. Plus, if we have continuous sequence whose length >= 3. Therefore, we want to use the del to reduce the replace operation.
   1. If we have aaa, where len % 3 == 0, we can reduce 1 replace by using 1 deletion
   2. If we have aaaa, where len % 3 == 1, we can reduce 1 replace by using 2 deletion
   3. If we have aaaaa, where len % 3 == 2, we can reduce 1 replace by using 3 deletion

Solution

Solution

Reference

Here