# Strong Password Checker
**Difficulty:** HARD
[External](https://leetcode.com/problems/strong-password-checker)
Canonical: https://scaleengineer.com/dsa/problems/strong-password-checker
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Heap (Priority Queue)
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Wix](https://scaleengineer.com/companies/wix), [Devtron](https://scaleengineer.com/companies/devtron)
---
## 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., `"B**aaa**bb0"` is weak, but `"B**aa**b**a**0"` 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 `'!'`.

# Approaches
## Brute-Force Search (BFS)
This approach treats the problem as a shortest path search in a vast state space of possible passwords. Starting from the given password, it explores all possible modifications (insert, delete, replace) layer by layer using a Breadth-First Search (BFS). The first time a strong password is found, the algorithm terminates, guaranteeing that the number of steps taken is the minimum possible. However, the number of possible passwords to check grows exponentially with each step, making this method computationally impractical.
**Time:** Exponential, O(B^D). The branching factor (number of possible next states) is very large, making the search explode in complexity very quickly. · **Space:** Exponential, O(B^D), where B is the branching factor and D is the solution depth. The `visited` set and queue can grow to an unmanageable size.
**Pros:** Guaranteed to find the absolute minimum number of steps.; Conceptually simple and straightforward to understand.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints.; Requires a massive amount of memory to store the `visited` set and the queue, leading to potential memory overflow.
### Explanation
The core idea is to build a state graph where each node is a unique password string. An edge connects two nodes if one password can be transformed into the other via a single operation (insertion, deletion, or replacement). The problem then becomes finding the shortest path from the initial password node to any node representing a strong password.

BFS is the natural algorithm for this, as it explores the graph level by level, guaranteeing that the first time we reach a goal state, it will be via a shortest path.

We start with a queue containing the initial password. We also use a `Set` to keep track of visited passwords to prevent redundant computations and infinite loops. The search proceeds in levels, where each level corresponds to one additional operation. For every password processed, we check if it's strong. If not, we generate all possible new passwords by applying one of the three operations at every possible position. These new, unvisited passwords are then added to the queue for the next level of the search.

```java
// Conceptual code for BFS approach
// Note: This is not a practical solution due to performance issues.
class Solution {
    public int strongPasswordChecker(String password) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(password);
        visited.add(password);
        int steps = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                String current = queue.poll();
                if (isStrong(current)) {
                    return steps;
                }
                // Generate all next possible passwords via one operation
                // (insert, delete, replace) and add to queue if not visited.
            }
            steps++;
        }
        return -1; // Should not be reached
    }

    private boolean isStrong(String s) {
        if (s.length() < 6 || s.length() > 20) return false;
        boolean hasLower = false, hasUpper = false, hasDigit = false;
        for (char c : s.toCharArray()) {
            if (Character.isLowerCase(c)) hasLower = true;
            if (Character.isUpperCase(c)) hasUpper = true;
            if (Character.isDigit(c)) hasDigit = true;
        }
        if (!hasLower || !hasUpper || !hasDigit) return false;
        for (int i = 0; i <= s.length() - 3; i++) {
            if (s.charAt(i) == s.charAt(i + 1) && s.charAt(i + 1) == s.charAt(i + 2)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
1. Model the problem as a shortest path problem on a graph where nodes are password strings and edges represent one operation (insert, delete, replace).
2. Use Breadth-First Search (BFS) to find the shortest path from the initial password to any strong password.
3. Initialize a queue with the starting password and a `visited` set to avoid cycles.
4. In each level of the BFS, explore all possible passwords that can be generated by one operation from the passwords in the current level.
5. For each password dequeued, check if it meets the strong password criteria.
6. If a strong password is found, the current level number (number of steps) is the minimum required, so return it.
7. If the password is not strong, generate all valid next states (by inserting, deleting, or replacing a character) and add them to the queue if they haven't been visited.

## One-Pass Greedy Approach
This is a highly efficient approach that solves the problem in a single pass by applying a greedy strategy. It first analyzes the password to determine all its deficiencies: length issues, missing character types, and consecutive repeating characters. Based on the password's length, it enters one of three logical paths (`n < 6`, `6 <= n <= 20`, or `n > 20`) and calculates the minimum changes by cleverly resolving the conflicts and overlaps between different types of required fixes.
**Time:** O(N), where N is the length of the password. The algorithm involves a single pass to gather statistics, followed by constant-time calculations. · **Space:** O(1), as we only use a few variables and a constant-size array (`repeats_mod`) to store the state, regardless of the input password's length.
**Pros:** Extremely efficient with linear time complexity.; Requires constant extra space, making it suitable for large inputs.; Provides the optimal solution by correctly applying a greedy strategy.
**Cons:** The logic is complex, particularly for the `n > 20` case, and requires careful handling of edge cases.; It can be difficult to prove the greedy choices are optimal without careful case analysis.
### Explanation
The algorithm's strength lies in its ability to correctly determine the minimum number of operations by understanding how they interact. Instead of exploring a vast search space, it directly calculates the result.

**Initial Analysis:**
First, we iterate through the password to find:
- `missing_types`: The number of required character types (lowercase, uppercase, digit) that are not present.
- `repeating_changes`: The number of replacements needed to break up sequences of three or more identical characters. For each such sequence of length `L`, we need `L/3` replacements. We also track the counts of these sequences based on their length modulo 3, which is crucial for the `n > 20` case.

**Case-based Logic:**
- **`n < 6`:** The primary issue is length. We need `6 - n` insertions. These insertions can simultaneously satisfy the `missing_types` requirement. Thus, the total operations needed is the maximum of these two values, as one operation can serve two purposes. Repeating sequences are not a concern as they will be broken by the necessary insertions/replacements.

- **`6 <= n <= 20`:** Length is not an issue. We only need to use replacements to fix `missing_types` and `repeating_changes`. Since one replacement can fix a repeating character and introduce a missing type, the total operations are the maximum of the two counts.

- **`n > 20`:** This is the most complex case. We must perform `n - 20` deletions. The greedy strategy is to use these deletions to fix the most 'expensive' repeating sequences first. A deletion is most valuable when it reduces the number of required replacements. The priority is:
    1. Delete 1 character from a sequence of length `L` where `L % 3 == 0`. This saves one replacement.
    2. Delete 2 characters from a sequence of length `L` where `L % 3 == 1`. This also saves one replacement.
    3. Any remaining deletions are used in groups of 3 to reduce the total length, which effectively saves one replacement per 3 deletions.
After applying deletions, the final number of steps is the `n - 20` deletions plus the number of replacements needed for any remaining issues, which is `max(missing_types, remaining_repeating_changes)`.

```java
class Solution {
    public int strongPasswordChecker(String password) {
        int n = password.length();
        int missing_types = 3;
        if (password.chars().anyMatch(Character::isLowerCase)) missing_types--;
        if (password.chars().anyMatch(Character::isUpperCase)) missing_types--;
        if (password.chars().anyMatch(Character::isDigit)) missing_types--;

        int repeating_changes = 0;
        // repeats_mod[i] will store the count of repeating sequences with length % 3 == i
        int[] repeats_mod = new int[3];
        for (int i = 0; i < n; ) {
            char c = password.charAt(i);
            int j = i;
            while (j < n && password.charAt(j) == c) {
                j++;
            }
            int len = j - i;
            if (len >= 3) {
                repeating_changes += len / 3;
                repeats_mod[len % 3]++;
            }
            i = j;
        }

        if (n < 6) {
            return Math.max(missing_types, 6 - n);
        } else if (n <= 20) {
            return Math.max(missing_types, repeating_changes);
        } else { // n > 20
            int deletions_needed = n - 20;
            int total_deletions = deletions_needed;

            // Use 1 deletion to fix a L%3==0 sequence (saves 1 replacement)
            int use_del = Math.min(deletions_needed, repeats_mod[0]);
            deletions_needed -= use_del;
            repeating_changes -= use_del;

            // Use 2 deletions to fix a L%3==1 sequence (saves 1 replacement)
            use_del = Math.min(deletions_needed / 2, repeats_mod[1]);
            deletions_needed -= use_del * 2;
            repeating_changes -= use_del;
            
            // Use 3 deletions to fix any sequence (saves 1 replacement)
            use_del = Math.min(deletions_needed / 3, repeating_changes);
            repeating_changes -= use_del;

            return total_deletions + Math.max(missing_types, repeating_changes);
        }
    }
}
```
### Algorithm
1. First, perform a single pass over the password to gather key metrics:
    - `n`: the length of the password.
    - `missing_types`: the number of missing character types (lowercase, uppercase, digit), from 0 to 3.
    - `repeating_changes`: the number of replacements needed to fix all repeating sequences. A sequence of length `L` needs `L/3` replacements.
    - For the `n > 20` case, also count how many repeating sequences have lengths `L` such that `L % 3 == 0`, `L % 3 == 1`, and `L % 3 == 2`.
2. Handle the problem in three distinct cases based on the password length `n`:
3. **Case 1: `n < 6`**
    - The password is too short. We need at least `6 - n` insertions. These insertions can also fix missing character types. The total steps will be the maximum of the changes needed for length and for character types.
    - Return `max(missing_types, 6 - n)`.
4. **Case 2: `6 <= n <= 20`**
    - The password length is acceptable. We only need to fix missing types and repeating characters using replacements. A single replacement can address both issues simultaneously.
    - Return `max(missing_types, repeating_changes)`.
5. **Case 3: `n > 20`**
    - The password is too long. We must perform `deletions_needed = n - 20` deletions.
    - Greedily use these deletions to reduce `repeating_changes` as efficiently as possible:
        - First, use 1 deletion on sequences where `len % 3 == 0` (saves 1 replacement).
        - Second, use 2 deletions on sequences where `len % 3 == 1` (saves 1 replacement).
        - Finally, use any remaining 3 deletions on any repeating sequence (saves 1 replacement).
    - After deletions, the remaining changes are `max(missing_types, remaining_repeating_changes)`.
    - Return `deletions_needed + max(missing_types, remaining_repeating_changes)`.

# Solutions
### Java

```java
class Solution {
public
  int strongPasswordChecker(String password) {
    int types = countTypes(password);
    int n = password.length();
    if (n < 6) {
      return Math.max(6 - n, 3 - types);
    }
    char[] chars = password.toCharArray();
    if (n <= 20) {
      int replace = 0;
      int cnt = 0;
      char prev = '~';
      for (char curr : chars) {
        if (curr == prev) {
          ++cnt;
        } else {
          replace += cnt / 3;
          cnt = 1;
          prev = curr;
        }
      }
      replace += cnt / 3;
      return Math.max(replace, 3 - types);
    }
    int replace = 0, remove = n - 20;
    int remove2 = 0;
    int cnt = 0;
    char prev = '~';
    for (char curr : chars) {
      if (curr == prev) {
        ++cnt;
      } else {
        if (remove > 0 && cnt >= 3) {
          if (cnt % 3 == 0) {
            --remove;
            --replace;
          } else if (cnt % 3 == 1) {
            ++remove2;
          }
        }
        replace += cnt / 3;
        cnt = 1;
        prev = curr;
      }
    }
    if (remove > 0 && cnt >= 3) {
      if (cnt % 3 == 0) {
        --remove;
        --replace;
      } else if (cnt % 3 == 1) {
        ++remove2;
      }
    }
    replace += cnt / 3;
    int use2 = Math.min(Math.min(replace, remove2), remove / 2);
    replace -= use2;
    remove -= use2 * 2;
    int use3 = Math.min(replace, remove / 3);
    replace -= use3;
    remove -= use3 * 3;
    return (n - 20) + Math.max(replace, 3 - types);
  }
private
  int countTypes(String s) {
    int a = 0, b = 0, c = 0;
    for (char ch : s.toCharArray()) {
      if (Character.isLowerCase(ch)) {
        a = 1;
      } else if (Character.isUpperCase(ch)) {
        b = 1;
      } else if (Character.isDigit(ch)) {
        c = 1;
      }
    }
    return a + b + c;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int strongPasswordChecker(string password) {
    int types = countTypes(password);
    int n = password.size();
    if (n < 6)
      return max(6 - n, 3 - types);
    if (n <= 20) {
      int replace = 0, cnt = 0;
      char prev = '~';
      for (char &curr : password) {
        if (curr == prev)
          ++cnt;
        else {
          replace += cnt / 3;
          cnt = 1;
          prev = curr;
        }
      }
      replace += cnt / 3;
      return max(replace, 3 - types);
    }
    int replace = 0, remove = n - 20;
    int remove2 = 0;
    int cnt = 0;
    char prev = '~';
    for (char &curr : password) {
      if (curr == prev)
        ++cnt;
      else {
        if (remove > 0 && cnt >= 3) {
          if (cnt % 3 == 0) {
            --remove;
            --replace;
          } else if (cnt % 3 == 1)
            ++remove2;
        }
        replace += cnt / 3;
        cnt = 1;
        prev = curr;
      }
    }
    if (remove > 0 && cnt >= 3) {
      if (cnt % 3 == 0) {
        --remove;
        --replace;
      } else if (cnt % 3 == 1)
        ++remove2;
    }
    replace += cnt / 3;
    int use2 = min(min(replace, remove2), remove / 2);
    replace -= use2;
    remove -= use2 * 2;
    int use3 = min(replace, remove / 3);
    replace -= use3;
    remove -= use3 * 3;
    return (n - 20) + max(replace, 3 - types);
  }
  int countTypes(string &s) {
    int a = 0, b = 0, c = 0;
    for (char &ch : s) {
      if (islower(ch))
        a = 1;
      else if (isupper(ch))
        b = 1;
      else if (isdigit(ch))
        c = 1;
    }
    return a + b + c;
  }
};

```

### Python

```python
class Solution:
    def strongPasswordChecker(self, password: str) -> int: def countTypes(s): a = b = c = 0 for ch in s: if ch . islower(): a = 1 elif ch . isupper(): b = 1 elif ch . isdigit(): c = 1 return a + b + c types = countTypes(password) n = len(password) if n < 6: return max(6 - n, 3 - types) if n <= 20: replace = cnt = 0 prev = '~' for curr in password: if curr == prev: cnt += 1 else: replace += cnt // 3 cnt = 1 prev = curr replace += cnt // 3 return max(replace, 3 - types) replace = cnt = 0 remove, remove2 = n - 20, 0 prev = '~' for curr in password: if curr == prev: cnt += 1 else: if remove > 0 and cnt >= 3: if cnt % 3 == 0: remove -= 1 replace -= 1 elif cnt % 3 == 1: remove2 += 1 replace += cnt // 3 cnt = 1 prev = curr if remove > 0 and cnt >= 3: if cnt % 3 == 0: remove -= 1 replace -= 1 elif cnt % 3 == 1: remove2 += 1 replace += cnt // 3 use2 = min(replace, remove2, remove // 2) replace -= use2 remove -= use2 * 2 use3 = min(replace, remove // 3) replace -= use3 remove -= use3 * 3 return n - 20 + max(replace, 3 - types)

```