# 4ms Commented Java solution

• This solution conceptualizes `insertions`, `deletions`, `breaks`, `additions`, and `changes`.

An `insertion` is when a character must be inserted, which only occurs when the given password is under `6` character long.
A `deletion` is when a character must be deleted, which only occurs when the given password is over `20` characters long.

A `break` is when a character must be inserted or replaced in order to meet the sequence-length requirements. Note that if our `deletions` are positive, we can use them to reduce the number of `breaks` we might need, before we have to do any character replacement.
An `addition` is when a character must be inserted or replaced in order to meet the alphanumeric requirements.

A `change` is the insertion, deletion, or replacement of any single character.

Having calculated how many `insertions`, `deletions`, `breaks`, and `additions` we need, we consolidate these to arrive at the minimum number of `changes`.

This code is long, but hopefully someone finds it useful:

``````public class Solution {
// The given String
String s;

// The number of additions which are required

// The number of deletions which are required
int numDeletions;

// The sequences we encounter
int[] seq;

/**
* Given a String s, the candidate password, returns the minimum number
* of single-action changes required for that password to be "strong".
*
* In order to be "strong," a password must:
* (1) be between 6 and 20 characters in length, inclusive,
* (2) contain at least one lowercase letter,
* (3) contain at least one uppercase letter.
* (4) contain at least one number.
* (5) not contain a sequence of 3 or more repeated characters
*
* The possible single-action changes are:
* (a) Delete a character,
* (b) Insert a character,
* (c) Replace a character with another character.
*
* Ex. "abc12" -> 1 since the password is missing one character, and that
*      character can be an uppercase letter.
*
* Ex. "aaabbb" -> 2 since we can change the middle 'a' and 'b' to 'H' and '1'.
*
* Ex. "Aa1Aa1Aa1Aa1Aa1Aa1zzAa1Aa1Aa1Aa1Aa1Aa1zzAa1Aa1Aa1Aa1Aa1Aa1zz" ->
*      40, since the password meets the strong criteria except that it is
*      60 characters long, so we must delete 40 characters.
*
* Ex. "\$\$\$\$\$\$" -> 3, since it's missing lowercase, uppercase, and a number,
*      and we can distribute those replacements to break the sequence of 6.
*
* @param s the given string
* @return the minimum number of changes to have a strong password
*/
if (s == null || s.equals("")) return 6;
this.s = s;

// Initialize instance variables
numDeletions = 0;
seq = new int[s.length() + 1];

// Count "additions" and frequency of sequences encountered

// Spend deletions to minimize sequence breaks needed, if possible
if (s.length() > 20) spendDeletions();

// Tally number of sequence breaks needed
int numBreaks = 0;
for (int i = 3; i < seq.length; i++) {
numBreaks += seq[i] * (i / 3);
}

// Consolidate breaks and additions into changes

// For too-short input, consolidate insertions and changes.
if (s.length() < 6) {
int numInsertions = 6 - s.length();
numChanges = Math.max(numInsertions, numChanges);
}

// For too-long input, add the number of breaks and additions needed
// to the number of deletions required.
else if (s.length() > 20) {
numChanges = numDeletions + numChanges;
}

return numChanges;
}

/**
* Processes the given string, storing whether the String meets the
* alphanumeric requirements, and storing the sequences of repeated
* characters, if 3 or longer.
*/
boolean needsNumber = true;
boolean needsUpper = true;
boolean needsLower = true;

// The current sequence length
int c = 1;
char tmp = s.charAt(0);
for (int i = 0; i < s.length(); i++) {
if (i > 0) {
// The sequence continues
if (s.charAt(i) == tmp) c++;

// The sequence has ended
else {
if (c > 2) seq[c]++;
c = 1;
tmp = s.charAt(i);
}
}
if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') needsLower = false;
else if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') needsUpper = false;
else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') needsNumber = false;
}

// Handle long sequences which continue to the end the given String
if (c > 2) seq[c]++;

}

/**
* Spends deletions to minimize the number of sequence breaks.
*
* Beginning at the last index of seq which is a multiple of three,
* count backwards through seq by threes to spend all deletions.
*
* a "break" by just deleting a single character at these indices.
* In other words, this is the best use of our deletions.
*
* Then, we start with the last index of seq which is one more than a
* multiple of three, since we can avoid adding a "break" by just
* deleting two characters at these indices.
* This is the next-best use of our deletions.
*
* Finally, we start with the last index of seq which is two more than a
* multiple of three, since we can avoid adding a "break" by just
* deleting three characters at these indices.
* This is the most costly way to spend our deletions.
*
* If we ever can't afford the full deletion at a given index, we spend
* our remaining deletions at that index for a single sequence.
*
* Counting backward allows us to spend all of our remaining deletions
* indiscriminately, like where all sequences cost 3 deletions to remove
* a single break.
*/
private void spendDeletions() {
numDeletions = s.length() - 20;
int ndtemp = numDeletions;
int lastThreeMult = 3 * ((seq.length - 1) / 3);
for (int i = lastThreeMult; i < lastThreeMult + 3; i++) {
// Handle falling off the back of seq
int j = (i >= seq.length) ? i - 3: i;
while (j > 2 && ndtemp > 0) {
if (seq[j] > 0) {

// We have one fewer sequence of length j
seq[j]--;

/**
* Determine whether we have enough deletions remaining
* in order to reduce the number of needed sequence breaks
* by 1.
*
* If we don't, just spend all remaining deletions.
* It won't affect our final "changes" tally.
*/
int d = Math.min((i % 3) + 1, ndtemp);

// We have one more sequence of length (j-d)
seq[j-d]++;

// Update our spent deletions
ndtemp -= d;
}
else j -= 3;
}
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.