Strong Password Checker

Problem#

A strong password (1) has length 6–20, (2) contains at least one lowercase, one uppercase, one digit, (3) has no three consecutive identical characters. Return the minimum number of single-char operations (insert, delete, replace) to make password strong.

Examples#

"a" → 5
"aA1" → 3
"1337C0d3" → 0

Hints#

Hint 1

Three independent constraints. Replacements can fix triplet runs AND missing character types simultaneously. Allocate carefully when length is wrong.

Approach#

Counts of missing categories (1–3). Find every run of ≥3 identical characters; each run of length L needs L / 3 replacements to break.

Cases:

length < 6: ops = max(missing, 6 - n). Inserts can fix missing too.
length 6..20: ops = max(missing, replacementsNeeded).
length > 20: must delete n - 20. Use deletions strategically on length-3k+0/1/2 runs to also reduce replacement needs, then ops = deletions + max(missing, residualReplacements).

Solution#

class Solution {
public:
    int strongPasswordChecker(string s) {
        int n = s.size();
        bool hasLow = false, hasUp = false, hasDig = false;
        for (char c : s) {
            if (islower(c)) hasLow = true;
            else if (isupper(c)) hasUp = true;
            else if (isdigit(c)) hasDig = true;
        }
        int missing = (!hasLow) + (!hasUp) + (!hasDig);

        vector<int> runs;
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) ++j;
            if (j - i >= 3) runs.push_back(j - i);
            i = j;
        }

        if (n < 6) {
            return max(missing, 6 - n);
        }
        if (n <= 20) {
            int replacements = 0;
            for (int r : runs) replacements += r / 3;
            return max(missing, replacements);
        }
        int over = n - 20;
        int deletions = over;
        // Use deletions to optimally reduce replacement counts.
        for (int k = 1; k <= 2 && over > 0; ++k) {
            for (auto& r : runs) {
                if (r >= 3 && r % 3 == k - 1 && over > 0) {
                    int use = min(over, k);
                    r -= use; over -= use;
                }
            }
        }
        for (auto& r : runs) {
            if (r >= 3 && over > 0) {
                int use = min(over, r - 2);
                r -= use; over -= use;
            }
        }
        int replacements = 0;
        for (int r : runs) replacements += r / 3;
        return deletions + max(missing, replacements);
    }
};

func strongPasswordChecker(s string) int {
    n := len(s)
    hasLow, hasUp, hasDig := false, false, false
    for i := 0; i < n; i++ {
        c := s[i]
        switch {
        case c >= 'a' && c <= 'z':
            hasLow = true
        case c >= 'A' && c <= 'Z':
            hasUp = true
        case c >= '0' && c <= '9':
            hasDig = true
        }
    }
    missing := 0
    if !hasLow {
        missing++
    }
    if !hasUp {
        missing++
    }
    if !hasDig {
        missing++
    }
    max := func(a, b int) int {
        if a > b {
            return a
        }
        return b
    }
    min := func(a, b int) int {
        if a < b {
            return a
        }
        return b
    }
    runs := []int{}
    for i := 0; i < n; {
        j := i
        for j < n && s[j] == s[i] {
            j++
        }
        if j-i >= 3 {
            runs = append(runs, j-i)
        }
        i = j
    }
    if n < 6 {
        return max(missing, 6-n)
    }
    if n <= 20 {
        replacements := 0
        for _, r := range runs {
            replacements += r / 3
        }
        return max(missing, replacements)
    }
    over := n - 20
    deletions := over
    // Use deletions to optimally reduce replacement counts.
    for k := 1; k <= 2 && over > 0; k++ {
        for i := range runs {
            if runs[i] >= 3 && runs[i]%3 == k-1 && over > 0 {
                use := min(over, k)
                runs[i] -= use
                over -= use
            }
        }
    }
    for i := range runs {
        if runs[i] >= 3 && over > 0 {
            use := min(over, runs[i]-2)
            runs[i] -= use
            over -= use
        }
    }
    replacements := 0
    for _, r := range runs {
        replacements += r / 3
    }
    return deletions + max(missing, replacements)
}

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        n = len(password)
        has_low = any(c.islower() for c in password)
        has_up = any(c.isupper() for c in password)
        has_dig = any(c.isdigit() for c in password)
        missing = (not has_low) + (not has_up) + (not has_dig)

        runs = []
        i = 0
        while i < n:
            j = i
            while j < n and password[j] == password[i]:
                j += 1
            if j - i >= 3:
                runs.append(j - i)
            i = j

        if n < 6:
            return max(missing, 6 - n)
        if n <= 20:
            replacements = sum(r // 3 for r in runs)
            return max(missing, replacements)

        over = n - 20
        deletions = over
        # Use deletions to optimally reduce replacement counts.
        for k in range(1, 3):
            if over <= 0:
                break
            for idx in range(len(runs)):
                if runs[idx] >= 3 and runs[idx] % 3 == k - 1 and over > 0:
                    use = min(over, k)
                    runs[idx] -= use
                    over -= use
        for idx in range(len(runs)):
            if runs[idx] >= 3 and over > 0:
                use = min(over, runs[idx] - 2)
                runs[idx] -= use
                over -= use
        replacements = sum(r // 3 for r in runs)
        return deletions + max(missing, replacements)

function strongPasswordChecker(password) {
    const n = password.length;
    let hasLow = false, hasUp = false, hasDig = false;
    for (const c of password) {
        if (c >= 'a' && c <= 'z') hasLow = true;
        else if (c >= 'A' && c <= 'Z') hasUp = true;
        else if (c >= '0' && c <= '9') hasDig = true;
    }
    const missing = (!hasLow ? 1 : 0) + (!hasUp ? 1 : 0) + (!hasDig ? 1 : 0);

    const runs = [];
    for (let i = 0; i < n;) {
        let j = i;
        while (j < n && password[j] === password[i]) j++;
        if (j - i >= 3) runs.push(j - i);
        i = j;
    }

    if (n < 6) return Math.max(missing, 6 - n);
    if (n <= 20) {
        let replacements = 0;
        for (const r of runs) replacements += Math.floor(r / 3);
        return Math.max(missing, replacements);
    }
    let over = n - 20;
    const deletions = over;
    // Use deletions to optimally reduce replacement counts.
    for (let k = 1; k <= 2 && over > 0; k++) {
        for (let i = 0; i < runs.length; i++) {
            if (runs[i] >= 3 && runs[i] % 3 === k - 1 && over > 0) {
                const use = Math.min(over, k);
                runs[i] -= use;
                over -= use;
            }
        }
    }
    for (let i = 0; i < runs.length; i++) {
        if (runs[i] >= 3 && over > 0) {
            const use = Math.min(over, runs[i] - 2);
            runs[i] -= use;
            over -= use;
        }
    }
    let replacements = 0;
    for (const r of runs) replacements += Math.floor(r / 3);
    return deletions + Math.max(missing, replacements);
}

class Solution {
    public int strongPasswordChecker(String password) {
        int n = password.length();
        boolean hasLow = false, hasUp = false, hasDig = false;
        for (int i = 0; i < n; i++) {
            char c = password.charAt(i);
            if (c >= 'a' && c <= 'z') hasLow = true;
            else if (c >= 'A' && c <= 'Z') hasUp = true;
            else if (c >= '0' && c <= '9') hasDig = true;
        }
        int missing = (hasLow ? 0 : 1) + (hasUp ? 0 : 1) + (hasDig ? 0 : 1);

        List<Integer> runs = new ArrayList<>();
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && password.charAt(j) == password.charAt(i)) j++;
            if (j - i >= 3) runs.add(j - i);
            i = j;
        }

        if (n < 6) return Math.max(missing, 6 - n);
        if (n <= 20) {
            int replacements = 0;
            for (int r : runs) replacements += r / 3;
            return Math.max(missing, replacements);
        }
        int over = n - 20;
        int deletions = over;
        // Use deletions to optimally reduce replacement counts.
        for (int k = 1; k <= 2 && over > 0; k++) {
            for (int i = 0; i < runs.size(); i++) {
                int r = runs.get(i);
                if (r >= 3 && r % 3 == k - 1 && over > 0) {
                    int use = Math.min(over, k);
                    runs.set(i, r - use);
                    over -= use;
                }
            }
        }
        for (int i = 0; i < runs.size(); i++) {
            int r = runs.get(i);
            if (r >= 3 && over > 0) {
                int use = Math.min(over, r - 2);
                runs.set(i, r - use);
                over -= use;
            }
        }
        int replacements = 0;
        for (int r : runs) replacements += r / 3;
        return deletions + Math.max(missing, replacements);
    }
}

function strongPasswordChecker(password: string): number {
    const n = password.length;
    let hasLow = false, hasUp = false, hasDig = false;
    for (const c of password) {
        if (c >= 'a' && c <= 'z') hasLow = true;
        else if (c >= 'A' && c <= 'Z') hasUp = true;
        else if (c >= '0' && c <= '9') hasDig = true;
    }
    const missing = (!hasLow ? 1 : 0) + (!hasUp ? 1 : 0) + (!hasDig ? 1 : 0);

    const runs: number[] = [];
    for (let i = 0; i < n;) {
        let j = i;
        while (j < n && password[j] === password[i]) j++;
        if (j - i >= 3) runs.push(j - i);
        i = j;
    }

    if (n < 6) return Math.max(missing, 6 - n);
    if (n <= 20) {
        let replacements = 0;
        for (const r of runs) replacements += Math.floor(r / 3);
        return Math.max(missing, replacements);
    }
    let over = n - 20;
    const deletions = over;
    // Use deletions to optimally reduce replacement counts.
    for (let k = 1; k <= 2 && over > 0; k++) {
        for (let i = 0; i < runs.length; i++) {
            if (runs[i] >= 3 && runs[i] % 3 === k - 1 && over > 0) {
                const use = Math.min(over, k);
                runs[i] -= use;
                over -= use;
            }
        }
    }
    for (let i = 0; i < runs.length; i++) {
        if (runs[i] >= 3 && over > 0) {
            const use = Math.min(over, runs[i] - 2);
            runs[i] -= use;
            over -= use;
        }
    }
    let replacements = 0;
    for (const r of runs) replacements += Math.floor(r / 3);
    return deletions + Math.max(missing, replacements);
}

Editorial#

The trick for length > 20 is that deletions help with replacement budget too — but only if applied to runs of the right length parity. A length-3k+0 run benefits most after one deletion (drops floor(L/3) by 1); 3k+1 needs two; 3k+2 needs three. Greedily prefer the cheapest reductions.

Complexity#

Time: O(n).
Space: O(n).

Problem#

Examples#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#