Validate password strength and repair
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a password policy—length between 8 and 20 characters; must include at least one lowercase letter, one uppercase letter, and one digit; and must not contain any character repeated three or more times consecutively—write a function that
(a) validates whether an input string is compliant and
(b) if not, returns the minimum number of edits (insert, delete, replace) needed to make it compliant along with one valid corrected password. Describe your algorithm, consider large inputs, and analyze time/space complexity.
Quick Answer: This question evaluates string-processing, constraint-satisfaction, and algorithm-design skills by requiring validation against multiple password rules and computation of the minimal edits (insert, delete, replace) needed for compliance.
A password is **compliant** when ALL of the following hold:
1. Its length is between 8 and 20 characters (inclusive).
2. It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
3. No character is repeated three or more times **consecutively** (e.g. `aaa` is not allowed).
Write `solution(password)` that returns a pair `[is_valid, min_edits]` where:
- `is_valid` is `True` if `password` is already compliant, otherwise `False`.
- `min_edits` is the **minimum number of single-character edits** — insert, delete, or replace — needed to transform `password` into a compliant one (0 when it is already compliant).
A valid corrected password can always be produced alongside `min_edits` (see the worked explanations), but because many distinct repairs achieve the same minimum, only the deterministic `[is_valid, min_edits]` pair is graded.
**Algorithm.** This is an adaptation of the classic *Strong Password Checker* greedy:
- If `len < 8`: every insertion both lengthens the string and can break a run or add a missing character type, so the answer is `max(8 - len, missing_types)`.
- If `8 <= len <= 20`: only replacements help. A run of `L` equal chars needs `L // 3` replacements to break, and a replacement can simultaneously satisfy a missing type, giving `max(missing_types, sum(L_i // 3))`.
- If `len > 20`: you must delete `len - 20` characters. Spend those deletions greedily on runs first (`run % 3 == 0` saves a replacement per 1 deletion, `== 1` per 2, `== 2` per 3), then add `max(missing_types, remaining_replacements)`.
Note in this problem `missing_types` is the count of the three required character classes that are absent.
**Multi-language templates** return `[isValid, minEdits]` (the non-Python templates encode `isValid` as `1/0`).
Constraints
- 0 <= len(password) <= 10^5
- password consists of printable ASCII characters (letters, digits, symbols).
- Required character classes are lowercase [a-z], uppercase [A-Z], and digit [0-9]; symbols count toward length only.
- A 'consecutive repeat' is three or more identical characters in a row.
Examples
Input: ("",)
Expected Output: [False, 8]
Explanation: Empty string: too short. Need 8 insertions which also supply the 3 required character types, so min edits = max(8-0, 3) = 8.
Input: ("aA1bB2cC",)
Expected Output: [True, 0]
Explanation: Length 8, has lower/upper/digit, no triple repeats -> already compliant, 0 edits.
Hints
- First classify by length: under 8 (insert-dominated), 8..20 (replace-only), or over 20 (must delete down to 20).
- A run of L identical characters needs floor(L/3) replacements to break; a single replacement can also supply a missing character type, so the in-range answer is max(missing_types, sum of floor(L/3)).
- When len > 20, spend the forced deletions to remove replacements as cheaply as possible: a run with length % 3 == 0 loses a replacement after 1 deletion, % 3 == 1 after 2, % 3 == 2 after 3 — handle those buckets in that order.