Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count how many of the four character types (digit, lowercase, uppercase, special) are missing. Each character you add can fix at most one missing type while also adding one to the length. So you need at least missingTypes additions for the types and at least 6 − length additions to reach length 6 — and a single addition counts toward both. The answer is therefore max(missingTypes, 6 − length). O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you see that one added character serves two purposes at once, so the answer is the max of the missing-type count and the length deficit — not their sum.
Where candidates slip
Returning missingTypes + lengthDeficit, which double-counts: a character added to reach length 6 can also be the missing digit or symbol.
How to stand out
Prove both directions: you need at least `missing` additions (each fixes ≤ 1 type) and at least `6 − n` (to reach length), and you can always achieve `max` by making the first few additions be the missing types.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:The answer is whichever bound is larger — additions count toward both.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Sum the Two Deficits (Naive — Wrong)
1Hint 1Explore hintHide hint
First instinct: count missing types, then separately count how many characters short of 6 you are, and add them.
2Hint 2Explore hintHide hint
Test it on "Ab1": missing = 1 (special), deficit = 3. Sum says 4 — but you can finish in 3. Why?
3Hint 3Explore hintHide hint
The special character you add to fix the missing type is also one of the characters that grows the length. The fixes overlap.
A · Core idea
The tempting first formula treats the two problems — missing types and short length — as independent and adds their costs.
Why it feels right. They look like separate tasks: 'add the missing types' and 'pad up to length 6'. Adding two independent costs is the default mental model.
Why it over-counts. The tasks are not independent. Every character you add to fix a missing type also increases the length by one. On "Ab1" (length 3), you're missing a special character and you're 3 short. If you add !, you've simultaneously supplied the missing special AND moved the length from 3 to 4. You then add 2 more arbitrary characters to reach 6. Total: 3, not 4. Summing pretends the special character didn't help the length, double-counting it.
The fix. Because each addition serves both goals, the minimum is whichever requirement is larger, not the total. When the length deficit ≥ missing types, the first missing of those padding characters can be chosen to be exactly the missing types — so length alone determines the count. When missing types > deficit, you must add at least that many characters anyway, which more than covers the length. Either way: max(missing, lengthDeficit).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "Ab1"Types
upper, lower, digit present; special missing
missing = 1Sum = 4 (incorrect); correct answer is 3C · Code with teaching comments
Reference implementation previewpublic int minimumNumber(int n, String password) { int missing = countMissingTypes(password); int lengthDeficit = Math.max(0, 6 - n); return missing + lengthDeficit; // BUG: double-counts overlapping additions }Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Summing independent-looking costs is the classic over-count trap. The moment one operation can satisfy two requirements, the lower bound becomes a max over the requirements, not a sum.
ComplexityO(n) time, O(1) space — Scanning the string to detect the four types is O(n); the arithmetic is O(1). The flaw is correctness, not complexity — it over-counts whenever both deficits are positive.
E · Edge cases and pitfalls3Adding the two deficits — over-counts whenever both are positive.Explore edge casesHide edge cases
Pitfalls
- Adding the two deficits — over-counts whenever both are positive.
- Believing 'fix types' and 'pad length' are separate jobs; they share characters.
- Passing the test cases where one deficit is 0 (sum == max there) and assuming it's correct.
Approach 2 of 2 · Optimal
max(missingTypes, lengthDeficit) (Optimal)
1Hint 1Explore hintHide hint
Detect in one pass which of the four types are present, then count the missing ones (0–4).
2Hint 2Explore hintHide hint
Compute the length deficit as max(0, 6 − n). Now think: can one added character satisfy a missing type and increase length at the same time?
3Hint 3Explore hintHide hint
Yes — so you need at least `missing` adds and at least `lengthDeficit` adds, and the same adds can serve both. The minimum is max(missing, lengthDeficit).
A · Core idea
Scan the password once to record whether it contains a digit, a lowercase letter, an uppercase letter, and a special character. The number of false flags is missing. Compute lengthDeficit = max(0, 6 − n). Return max(missing, lengthDeficit).
Lower bound from types. Each added character is a single character, so it can introduce at most one new type. If missing types are absent, you cannot possibly fix them with fewer than missing additions. So the answer is ≥ missing.
Lower bound from length. A strong password needs length ≥ 6. If the current length is n < 6, you must add at least 6 − n characters. So the answer is ≥ lengthDeficit. Therefore the answer is ≥ max(missing, lengthDeficit) — both bounds must hold.
Why `max` is also achievable (upper bound). Consider the larger of the two. If lengthDeficit ≥ missing, you're going to add lengthDeficit characters to reach length 6 anyway — and you're free to choose what they are. Make the first missing of them be exactly the missing types; the remaining lengthDeficit − missing can be anything. After those lengthDeficit additions, all types are present and the length is 6 — strong. If instead missing > lengthDeficit, you add missing characters (one per missing type); that already pushes the length to n + missing ≥ n + (6 − n) = 6 because missing > 6 − n, so the length requirement is met for free. In both cases max(missing, lengthDeficit) additions suffice.
Lower bound meets upper bound. The answer is at least max(...) and at most max(...), so it equals max(missing, lengthDeficit). That two-sided argument is exactly what makes this provably optimal rather than a lucky formula.
Why clamp the deficit at 0. If n ≥ 6, then 6 − n ≤ 0; without the max(0, …) a negative deficit could wrongly drag the answer below missing. Clamping keeps the length bound from ever being negative.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "4700", n = 4Hash-map state
after scan
Continue scanning
only digits seen → 3 types missing
3C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Two requirements, one unit of work each, and the work overlaps → the cost is the max of the two lower bounds. Proving it both ways (you can't do fewer than max; you can always achieve max) is the discipline that separates a guessed formula from a justified one.
ComplexityO(n) time, O(1) space — One scan over the password sets four boolean flags in O(n); everything else is constant-time arithmetic. O(n) time, O(1) extra space (four booleans and a couple of ints).
E · Edge cases and pitfalls7s = "Strong#1", n = 8 — All four types present, length ≥ 6 → missing = 0, deficit = 0 → 0.Explore edge casesHide edge cases
Edge cases handled
s = "Strong#1", n = 8All four types present, length ≥ 6 → missing = 0, deficit = 0 → 0.s = "" (n = 0, if allowed)missing = 4, deficit = 6 → max(4, 6) = 6.s = "aaaaaa", n = 6Length fine; missing digit, upper, special → max(3, 0) = 3.s = "Ab1!", n = 4All types present, deficit 2 → max(0, 2) = 2.
Pitfalls
- Returning the sum instead of the max — double-counts overlapping additions.
- Forgetting max(0, 6 − n), letting a negative deficit corrupt the result.
- Mis-defining 'special' (e.g. treating '_' as special when it isn't in the set).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int minimumNumber(int n, String password) { boolean hasDigit = false, hasLower = false, hasUpper = false, hasSpecial = false; String special = "!@#$%^&*()-+"; for (int i = 0; i < password.length(); i++) { char c = password.charAt(i);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Summing the two deficits
A character added to reach length 6 can also be the missing digit or special, so the two needs overlap. Summing charges for that character twice.
Explore the code comparisonHide the code comparison
Summing the two deficits
A character added to reach length 6 can also be the missing digit or special, so the two needs overlap. Summing charges for that character twice.
Don't write this
return missing + Math.max(0, 6 - n);Write this instead
return Math.max(missing, Math.max(0, 6 - n));2Negative length deficit
For n ≥ 6, 6 − n is negative; without clamping it can pull the max below the true missing-type count.
Explore the code comparisonHide the code comparison
Negative length deficit
For n ≥ 6, 6 − n is negative; without clamping it can pull the max below the true missing-type count.
Don't write this
return max(missing, 6 - n)Write this instead
return max(missing, max(0, 6 - n))3Wrong special-character set
If your 'special' test admits characters outside !@#$%^&*()-+ (or rejects ones inside it), you'll mis-detect the special type and return a wrong count.
Explore the code comparisonHide the code comparison
Wrong special-character set
If your 'special' test admits characters outside !@#$%^&*()-+ (or rejects ones inside it), you'll mis-detect the special type and return a wrong count.
Don't write this
has_special = any(not c.isalnum() for c in password) # admits any non-alphanumericWrite this instead
special = set("!@#$%^&*()-+")
has_special = any(c in special for c in password)Revise
Carry the pattern into the interview
Pattern to remember
max(missing-type count, length deficit) — overlapping greedy bounds
Code pattern to memorize
missing = (noDigit?1:0) + (noLower?1:0)
+ (noUpper?1:0) + (noSpecial?1:0)
lengthDeficit = max(0, 6 - n)
return max(missing, lengthDeficit)Rules to remember
- 1There are exactly four required types: digit, lowercase, uppercase, special. Count how many are absent →
missing(0–4). - 2The length floor is 6:
lengthDeficit = max(0, 6 − n). - 3The answer is
max(missing, lengthDeficit), not their sum — each added char both supplies a missing type and grows the length. - 4Take
max(0, …)on the deficit: if the password is already ≥ 6, the length contributes nothing. - 5Define 'special' precisely (the problem's set is
!@#$%^&*()-+); a char is special iff it's none of digit/lower/upper within that set.
Use this pattern when
- You must satisfy several independent requirements with one cheap operation each
- A single action can satisfy more than one requirement simultaneously
- You want the minimum number of operations, and requirements overlap
- Two independent lower bounds exist and the optimum is whichever binds harder
Choose another pattern when
- Each fix can satisfy only one requirement → the answer is the sum, not the max
- Requirements conflict (fixing one breaks another) → greedy bounds don't apply
- You must output the actual strengthened password, not just the count → you build it
- Length cap or 'no 3 repeating' rules (LeetCode 420) → richer greedy with more cases
Interview takeaway
When several requirements can each be satisfied by the same unit of work, the minimum cost is the max of the individual lower bounds, not their sum — because the work overlaps. Recognising overlapping bounds is the whole trick here.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternOverlapping greedy lower bounds. When several requirements can each be met by the same unit of work, the minimum cost is the max of the individual bounds, not their sum. Prove optimality both ways: you can't beat the larger bound, and you can always realise it by letting padding work double as type-fixing.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Strong Password CheckerComing soonAdds a length cap (≤ 20) and a 'no 3 repeating characters' rule — a much richer greedy with replacements and deletions.
- Return a strong password, not just the countComing soonAppend the missing types first, then pad to length 6 — the constructive version.
- Configurable rule setComing soonGeneralise to k required categories and a min length m: answer = max(missing, max(0, m − n)).
- Minimum edits with replacements allowedComing soonIf you may replace characters, the overlap analysis changes — count toward both type and constraint differently.