Strong Password Checker - Solution & Explanation

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.