Strong Password Checker

Twice the number of downvotes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

import itertools

class Solution:
    lowercase = set('abcdefghijklmnopqrstuvwxyz')
    uppercase = set('ABCDEFGHIJKLMNOPQRSTUFVWXYZ')
    digit = set('0123456789')

    def strongPasswordChecker(self, s: str) -> int:
        characters = set(s)

        # Check rule (2)
        needs_lowercase = not (characters & self.lowercase)
        needs_uppercase = not (characters & self.uppercase)
        needs_digit = not (characters & self.digit)
        num_required_type_replaces = int(needs_lowercase + needs_uppercase + needs_digit)

        # Check rule (1)
        num_required_inserts = max(0, 6 - len(s))
        num_required_deletes = max(0, len(s) - 20)

        # Check rule (3)
        # Convert s to a list of repetitions for us to manipulate
        # For s = '11aaabB' we have groups = [2, 3, 1, 1]
        groups = [len(list(grp)) for _, grp in itertools.groupby(s)]

        # We apply deletions iteratively and always choose the best one.
        # This should be fine for short passwords :)
        # A delete is better the closer it gets us to removing a group of three.
        # Thus, a group needs to be (a) larger than 3 and (b) minimal wrt modulo 3.
        def apply_best_delete():
            argmin, _ = min(
                enumerate(groups),
                # Ignore groups of length < 3 as long as others are available.
                key=lambda it: it[1] % 3 if it[1] >= 3 else 10 - it[1],
            )
            groups[argmin] -= 1

        for _ in range(num_required_deletes):
            apply_best_delete()

        # On the finished groups, we need one repace per 3 consecutive letters.
        num_required_group_replaces = sum(
            group // 3
            for group in groups
        )

        return (
            # Deletes need to be done anyway
            num_required_deletes
            # Type replaces can be eaten up by inserts or group replaces.
            # Note that because of the interplay of rules (1) and (2), the required number of group replaces
            # can never be greater than the number of type replaces and inserts for candidates of length < 6.
            + max(
                num_required_type_replaces,
                num_required_group_replaces,
                num_required_inserts,
            )
        )

10 Prerequisite LeetCode Problems

“Strong Password Checker” requires string manipulation skills, attention to edge cases, and understanding of greedy algorithms. Here are 10 problems to build these foundational skills:

1. “Reverse String” (LeetCode Problem #344): This problem introduces the basics of string manipulation.

2. “Valid Anagram” (LeetCode Problem #242): This problem provides practice for basic string manipulation and character counting.

3. “Longest Substring Without Repeating Characters” (LeetCode Problem #3): This problem gives practice on string traversal and counting characters, which is useful for the “Strong Password Checker” problem.

4. “Minimum Moves to Equal Array Elements” (LeetCode Problem #453): This problem introduces a similar greedy approach used in the “Strong Password Checker” problem.

5. “Add Binary” (LeetCode Problem #67): This problem helps you practice formatting output strings and handling edge cases.

6. “Remove All Adjacent Duplicates In String” (LeetCode Problem #1047): This problem provides practice on handling repetitive characters in a string, a concept similar to the “Strong Password Checker” problem.

7. “Task Scheduler” (LeetCode Problem #621): This problem introduces the concept of arranging items (or characters, in the case of “Strong Password Checker”) to satisfy certain conditions, in a greedy manner.

8. “Candy” (LeetCode Problem #135): This problem involves a greedy algorithm and handling edge cases, similar to “Strong Password Checker”.

9. “Jump Game II” (LeetCode Problem #45): This problem helps to understand the concept of taking minimum steps to achieve a goal, similar to the minimum operations needed in “Strong Password Checker”.

10. “Gas Station” (LeetCode Problem #134): This problem involves finding an optimal solution in a circular structure using a greedy approach.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import itertools

class Solution:
    lowercase = set('abcdefghijklmnopqrstuvwxyz')
    uppercase = set('ABCDEFGHIJKLMNOPQRSTUFVWXYZ')
    digit = set('0123456789')

    def strongPasswordChecker(self, s: str) -> int:
        characters = set(s)

        needs_lowercase = not (characters & self.lowercase)
        needs_uppercase = not (characters & self.uppercase)
        needs_digit = not (characters & self.digit)
        num_required_type_replaces = int(needs_lowercase + needs_uppercase + needs_digit)

        num_required_inserts = max(0, 6 - len(s))
        num_required_deletes = max(0, len(s) - 20)

        groups = [len(list(grp)) for _, grp in itertools.groupby(s)]

        def apply_best_delete():
            argmin, _ = min(
                enumerate(groups),
                key=lambda it: it[1] % 3 if it[1] >= 3 else 10 - it[1],
            )
            groups[argmin] -= 1

        for _ in range(num_required_deletes):
            apply_best_delete()

        num_required_group_replaces = sum(
            group // 3
            for group in groups
        )

        return (
            num_required_deletes
            + max(
                num_required_type_replaces,
                num_required_group_replaces,
                num_required_inserts,
            )
        )

Problem Classification

Strong Password Checker - This problem requires checking the strength of a password based on some rules. This is a Password Strength Checking Problem.

Language Agnostic Coding Drills

1. Sets and Set Operations: The Python set data structure is a collection of unique elements. It supports various operations like union (&), intersection (|), difference (-), symmetric difference (^), and checking for subset (<=) or superset (>=). Here, set is used to store different types of characters.

2. String Operations: Basic string operations include indexing, slicing, concatenation, repetition, membership testing, formatting, etc. Here, strings are used to hold different sets of characters.

3. Logical Operations: These are boolean operations, like ‘and’, ‘or’, ’not’, etc. In this solution, ’not’ operation is used.

4. Boolean to Integer Conversion: In Python, True can be considered as 1 and False as 0 for arithmetic operations. This is used here to calculate num_required_type_replaces.

5. List Operations: Basic list operations include indexing, slicing, modifying, concatenation, repetition, membership testing, etc. Here, a list of group lengths is used.

6. Itertools Groupby: The Python itertools.groupby function is used to group consecutive elements that are same in an iterable. It’s a powerful tool for organizing and analyzing data.

7. Looping Constructs: Loops are used to repeat a block of code multiple times. Here, a for loop is used to apply the best delete operation.

8. List Comprehension: This is a compact way of creating a new list by performing an operation on each item in an existing list.

9. Enumerate Function: This function adds a counter to an iterable and returns it. The returned object is an enumerate object.

10. Lambda Functions: These are small anonymous functions that are created using the lambda keyword.

11. Min Function: This function is used to find the minimum item in an iterable or the minimum of two or more arguments.

12. Sum Function: This function returns the sum of all items in an iterable.

Given these concepts, the overall problem-solving approach can be described as follows:

1. Identify the types of characters that are missing in the given password.

2. Calculate the number of inserts and deletes required to make the password of a valid length (6-20 characters).

3. Group the same consecutive characters in the password and calculate the number of groups.

4. If the password length exceeds 20, delete the best character from the groups until the length becomes 20. Here, the best character is determined by the operation that minimizes the total replacements in all groups.

5. Calculate the number of replacements needed for each group to avoid having three consecutive same characters.

6. Return the total operations required, which is the sum of the number of deletes and the maximum of the number of type replacements, group replacements, and inserts.

Targeted Drills in Python

1. Sets and Set Operations

Drill: Create two sets and perform union, intersection, difference, and symmetric difference operations on them.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

set1 = set([1, 2, 3, 4])
set2 = set([3, 4, 5, 6])

# Union
print(set1 | set2)

# Intersection
print(set1 & set2)

# Difference
print(set1 - set2)

# Symmetric Difference
print(set1 ^ set2)

2. String Operations

Drill: Perform indexing, slicing, concatenation, repetition, and membership testing operations on a string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

s = "Hello, World!"

# Indexing
print(s[0])

# Slicing
print(s[0:5])

# Concatenation
print(s + " How are you?")

# Repetition
print(s * 2)

# Membership testing
print("World" in s)

3. Logical Operations

Drill: Practice logical operations with boolean values.

1
2
3

print(True and False)
print(True or False)
print(not True)

4. Boolean to Integer Conversion

Drill: Convert boolean values to integer and perform arithmetic operations.

1
2
3

print(int(True))
print(int(False))
print(int(True) + int(False))

5. List Operations

Drill: Perform indexing, slicing, modifying, concatenation, repetition, and membership testing operations on a list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

l = [1, 2, 3, 4]

# Indexing
print(l[0])

# Slicing
print(l[0:2])

# Modifying
l[0] = 0
print(l)

# Concatenation
print(l + [5, 6, 7])

# Repetition
print(l * 2)

# Membership testing
print(3 in l)

6. Itertools Groupby

Drill: Group consecutive same elements in a list using itertools.groupby.

1
2
3
4
5

import itertools

s = "AAAABBBCCDAABBB"
groups = [list(grp) for _, grp in itertools.groupby(s)]
print(groups)

7. Looping Constructs

Drill: Use a for loop to print numbers from 1 to 10.

1
2

for i in range(1, 11):
    print(i)

8. List Comprehension

Drill: Use list comprehension to create a list of squares of numbers from 1 to 10.

1
2

squares = [x**2 for x in range(1, 11)]
print(squares)

9. Enumerate Function

Drill: Use enumerate function to print index and value of elements in a list.

1
2
3
4

l = ['a', 'b', 'c', 'd', 'e']

for i, val in enumerate(l):
    print(f"Index: {i}, Value: {val}")

10. Lambda Functions

Drill: Use a lambda function to square a number.

1
2

square = lambda x: x**2
print(square(5))

11. Min Function

Drill: Use min function to find the smallest number in a list.

1
2

l = [5, 3, 2, 6, 1, 7]
print(min(l))

12. Sum Function

Drill: Use sum

function to find the sum of all numbers in a list.

1
2

l = [1, 2, 3, 4, 5]
print(sum(l))