420. Strong Password Checker Solution Guide

Q: Is Strong Password Checker easy or hard?

Strong Password Checker is rated Hard because it combines multiple constraints: length limits, character type requirements, and repetition rules. The challenge is designing a greedy strategy that minimizes edits while handling all cases efficiently.

Q: Strong Password Checker Python/Java solution

Python and Java implementations typically follow the greedy replacement strategy. The code scans the string, counts repeating groups, and applies insert, delete, or replace operations depending on length and missing character types. Both implementations achieve O(n) time complexity.

Q: How to solve Strong Password Checker in O(n)?

Traverse the password once and track three values: missing character types, lengths of repeating segments, and total length. Use greedy rules to determine how many insertions, deletions, or replacements are needed. When length exceeds 20, apply deletions to repeating sequences first to minimize future replacements.

Q: What is the best approach for Strong Password Checker?

The best approach is a greedy strategy that tracks missing character types, repeating sequences, and password length in one pass. Replacements handle repeating characters, insertions fix short passwords, and deletions reduce length and repetition in long passwords. This solution runs in O(n) time and O(1) space.

Q: Is Strong Password Checker asked at Google/Amazon/Meta?

Strong Password Checker is considered a high-difficulty string and greedy optimization problem similar to questions asked at companies like Google and Meta. It tests constraint handling, greedy reasoning, and careful case analysis, which are common interview themes.

Q: What data structure is used in Strong Password Checker?

Most optimal implementations only use counters and simple variables, making it primarily a greedy string problem. Some variations use a priority queue (heap) to prioritize deletions in repeating segments, but this is optional and not required for the O(n) solution.

Q: What is the time complexity of Strong Password Checker?

The optimal solution runs in O(n) time where n is the password length. The algorithm scans the string once to detect repeating sequences and missing character categories. Space complexity is O(1) because only counters and small variables are maintained.

The problem

A password is considered strong if the below conditions are all met:

It has at least 6 characters and at most 20 characters.
It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
It does not contain three repeating characters in a row (i.e., "Baaabb0" is weak, but "Baaba0" is strong).

Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.

In one step, you can:

Insert one character to password,
Delete one character from password, or
Replace one character of password with another character.

Example 1:

Input: password = "a"
Output: 5

Example 2:

Input: password = "aA1"
Output: 3

Example 3:

Input: password = "1337C0d3"
Output: 0

Constraints:

1 <= password.length <= 50
password consists of letters, digits, dot '.' or exclamation mark '!'.

Approach overview

Problem Overview: You are given a password string and must return the minimum number of changes required to make it a strong password. A strong password must have length between 6 and 20, contain at least one lowercase letter, one uppercase letter, and one digit, and must not contain three repeating characters in a row.

Approach 1: Greedy Approach with Replacements (O(n) time, O(1) space)

This method scans the string once while tracking three things: missing character types (lowercase, uppercase, digit), repeating sequences, and the current length of the password. For repeating runs like aaa or bbbb, you count how many replacements are required using length / 3. When the password is shorter than 6, insertions fix both length and missing character types. When it exceeds 20 characters, deletions are prioritized inside long repeating sequences because removing characters reduces the number of replacements required. The greedy insight is that deletions should target sequences where they reduce replacement cost the most. This strategy efficiently balances insert, delete, and replace operations using rules derived from repetition lengths. The algorithm processes the string in O(n) time and constant extra space, making it the standard optimal solution for this string and greedy problem.

Approach 2: Iterative Character Update (O(n) time, O(1) space)

This approach also walks through the password but directly simulates corrections step by step. You track missing character classes and detect repeating groups during iteration. Instead of calculating all operations mathematically upfront, the algorithm progressively updates counts for insertions, deletions, and replacements as it encounters violations. For long passwords, extra characters are removed while prioritizing sections with repeating patterns. For shorter ones, insertions are used to both extend the password and break repetition sequences. The method is straightforward to implement and works well in languages like C++ and JavaScript where iterative mutation is convenient.

Heap Optimization (conceptual extension): Some implementations push repeating segment lengths into a heap (priority queue). During deletion phases for passwords longer than 20, segments that benefit most from deletion are processed first. While not required for the optimal solution, this structure helps visualize the greedy prioritization.

Recommended for interviews: The greedy replacement strategy is what most interviewers expect. It demonstrates that you understand how to combine constraints—length limits, character diversity, and repetition rules—into a single linear pass. Brute reasoning about each constraint separately is useful during discussion, but the greedy solution shows the ability to optimize operations and reach the minimal number of edits.

Approach 1: Greedy Approach with Replacements

This approach works by identifying deficiencies in the password (length, missing character types, consecutive characters) and addressing them by replacements wherever necessary to minimize the number of operations required.

Python

def strongPasswordChecker(password: str) -> int:
    n = len(password)
    has_lower = any(c.islower() for c in password)
    has_upper = any(c.isupper() for c in password)
    has_digit = any(c.isdigit() for c in password)

    missing_types = 3 - sum([has_lower, has_upper, has_digit])

    change_count = 0
    one = two = 0
    p = 2
    while p < n:
        if password[p] == password[p - 1] == password[p - 2]:
            length = 2
            while p < n and password[p] == password[p - 1]:
                length += 1
                p += 1
            change_count += length // 3
            if length % 3 == 0:
                one += 1
            elif length % 3 == 1:
                two += 1
        else:
            p += 1

    if n < 6:
        return max(missing_types, 6 - n)
    elif n <= 20:
        return max(missing_types, change_count)
    else:
        delete_count = n - 20
        change_count -= min(delete_count, one)
        change_count -= min(max(delete_count - one, 0), two * 2) // 2
        change_count -= max(delete_count - one - 2 * two, 0) // 3
        return delete_count + max(missing_types, change_count)

Java

class Solution {
    public int strongPasswordChecker(String password) {
        int n = password.length();
        boolean hasLower = false, hasUpper = false, hasDigit = false;
        for (char c : password.toCharArray()) {
            if (Character.isLowerCase(c)) hasLower = true;
            if (Character.isUpperCase(c)) hasUpper = true;
            if (Character.isDigit(c)) hasDigit = true;
        }
        int missingTypes = (hasLower ? 0 : 1) + (hasUpper ? 0 : 1) + (hasDigit ? 0 : 1);

        int changeCount = 0, one = 0, two = 0;
        for (int i = 2; i < n;) {
            if (password.charAt(i) == password.charAt(i - 1) && password.charAt(i - 1) == password.charAt(i - 2)) {
                int length = 2;
                while (i < n && password.charAt(i) == password.charAt(i - 1)) {
                    length++;
                    i++;
                }
                changeCount += length / 3;
                if (length % 3 == 0) one++;
                else if (length % 3 == 1) two++;
            } else {
                i++;
            }
        }

        if (n < 6) {
            return Math.max(missingTypes, 6 - n);
        } else if (n <= 20) {
            return Math.max(missingTypes, changeCount);
        } else {
            int deleteCount = n - 20;
            changeCount -= Math.min(deleteCount, one);
            changeCount -= Math.min(Math.max(deleteCount - one, 0), two * 2) / 2;
            changeCount -= Math.max(deleteCount - one - 2 * two, 0) / 3;
            return deleteCount + Math.max(missingTypes, changeCount);
        }
    }
}

The Python solution uses a greedy approach to check the password's strength. It calculates missing character types, identifies repeating sequences, and determines necessary changes using minimal operations. If the length exceeds 20, deletions reduce the repeating sequences first.

Complexity

Time Complexity: O(n), where n is the length of the password.
Space Complexity: O(1), in-place computation.

Try this approach in the editor

Approach 2: Iterative Character Update

This approach iteratively processes sections of the password and applies necessary operations to resolve length, character type, and repeating character issues, one section at a time.

C++

#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int strongPasswordChecker(string password) {
        int n = password.size();
        bool hasLower = false, hasUpper = false, hasDigit = false;
        for (char c : password) {
            hasLower = hasLower || islower(c);
            hasUpper = hasUpper || isupper(c);
            hasDigit = hasDigit || isdigit(c);
        }
        int missingTypes = !hasLower + !hasUpper + !hasDigit;

        int toChange = 0, one = 0, two = 0;
        for (int i = 2; i < n;) {
            if (password[i] == password[i - 1] && password[i - 1] == password[i - 2]) {
                int length = 2;
                while (i < n && password[i] == password[i - 1]) {
                    length++;
                    i++;
                }
                toChange += length / 3;
                if (length % 3 == 0) one++;
                else if (length % 3 == 1) two++;
            } else {
                i++;
            }
        }

        if (n < 6) {
            return max(missingTypes, 6 - n);
        } else if (n <= 20) {
            return max(missingTypes, toChange);
        } else {
            int deleteCount = n - 20;
            toChange -= min(deleteCount, one);
            toChange -= min(max(deleteCount - one, 0), two * 2) / 2;
            toChange -= max(deleteCount - one - 2 * two, 0) / 3;
            return deleteCount + max(missingTypes, toChange);
        }
    }
};

JavaScript

function strongPasswordChecker(password) {
    let n = password.length;
    let hasLower = /[a-z]/.test(password);
    let hasUpper = /[A-Z]/.test(password);
    let hasDigit = /[0-9]/.test(password);
    let missingTypes = +!hasLower + +!hasUpper + +!hasDigit;

    let changeCount = 0, one = 0, two = 0;
    for (let i = 2; i < n;) {
        if (password[i] === password[i - 1] && password[i - 1] === password[i - 2]) {
            let length = 2;
            while (i < n && password[i] === password[i - 1]) {
                length++;
                i++;
            }
            changeCount += Math.floor(length / 3);
            if (length % 3 === 0) one++;
            else if (length % 3 === 1) two++;
        } else {
            i++;
        }
    }

    if (n < 6) {
        return Math.max(missingTypes, 6 - n);
    } else if (n <= 20) {
        return Math.max(missingTypes, changeCount);
    } else {
        let deleteCount = n - 20;
        changeCount -= Math.min(deleteCount, one);
        changeCount -= Math.min(Math.max(deleteCount - one, 0), two * 2) / 2;
        changeCount -= Math.max(deleteCount - one - 2 * two, 0) / 3;
        return deleteCount + Math.max(missingTypes, changeCount);
    }
}

The C++ method works similarly by processing input iteratively to calculate necessary change operations with attention to minimizing repetitive sections and enforcing character requirements.

Complexity

Time Complexity: O(n), where n is the length of the password.
Space Complexity: O(1), in-place solution.

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Replacements	Time Complexity: O(n), where n is the length of the password. Space Complexity: O(1), in-place computation.
Iterative Character Update	Time Complexity: O(n), where n is the length of the password. Space Complexity: O(1), in-place solution.

Complexity analysis

Approach	Time	Space	When to Use
Greedy Replacement Strategy	O(n)	O(1)	Best overall solution. Handles length constraints and repetition optimally.
Iterative Character Update	O(n)	O(1)	Good when implementing logic step‑by‑step in languages like C++ or JavaScript.
Heap-Based Greedy Optimization	O(n log n)	O(n)	Useful for visualizing deletion priorities across repeating segments.

Frequently asked questions

Is Strong Password Checker easy or hard?

Strong Password Checker is rated Hard because it combines multiple constraints: length limits, character type requirements, and repetition rules. The challenge is designing a greedy strategy that minimizes edits while handling all cases efficiently.

Strong Password Checker Python/Java solution

Python and Java implementations typically follow the greedy replacement strategy. The code scans the string, counts repeating groups, and applies insert, delete, or replace operations depending on length and missing character types. Both implementations achieve O(n) time complexity.

How to solve Strong Password Checker in O(n)?

Traverse the password once and track three values: missing character types, lengths of repeating segments, and total length. Use greedy rules to determine how many insertions, deletions, or replacements are needed. When length exceeds 20, apply deletions to repeating sequences first to minimize future replacements.

What is the best approach for Strong Password Checker?

The best approach is a greedy strategy that tracks missing character types, repeating sequences, and password length in one pass. Replacements handle repeating characters, insertions fix short passwords, and deletions reduce length and repetition in long passwords. This solution runs in O(n) time and O(1) space.

Is Strong Password Checker asked at Google/Amazon/Meta?

Strong Password Checker is considered a high-difficulty string and greedy optimization problem similar to questions asked at companies like Google and Meta. It tests constraint handling, greedy reasoning, and careful case analysis, which are common interview themes.

What data structure is used in Strong Password Checker?

Most optimal implementations only use counters and simple variables, making it primarily a greedy string problem. Some variations use a priority queue (heap) to prioritize deletions in repeating segments, but this is optional and not required for the O(n) solution.

What is the time complexity of Strong Password Checker?

The optimal solution runs in O(n) time where n is the password length. The algorithm scans the string once to detect repeating sequences and missing character categories. Space complexity is O(1) because only counters and small variables are maintained.

Strong Password Checker solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Replacements

Approach 2: Iterative Character Update

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Strong Password Checker solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Replacements

Approach 2: Iterative Character Update

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems