LeetCode 420. 强密码检验器

Categories:

题目描述
思路分析
1. 解法一：分类计数 + 贪心删除（推荐）
相似题目

题目描述

✅ 420. 强密码检验器

思路分析

解法一：分类计数 + 贪心删除（推荐）

核心思路：

统计缺失字符类型数 missing（小写/大写/数字）。

统计所有连续重复段长度 len，其需要的替换次数为 len / 3。

当 n > 20 时必须删除，优先对 len % 3 == 0/1/2 的段按删除收益顺序处理，以最大化减少替换次数。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)。

class Solution {
    public int strongPasswordChecker(String s) {
        int n = s.length();
        boolean hasLower = false;
        boolean hasUpper = false;
        boolean hasDigit = false;

        // 统计字符种类缺失
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (Character.isLowerCase(ch)) {
                hasLower = true;
            } else if (Character.isUpperCase(ch)) {
                hasUpper = true;
            } else if (Character.isDigit(ch)) {
                hasDigit = true;
            }
        }

        int missing = (hasLower ? 0 : 1) + (hasUpper ? 0 : 1) + (hasDigit ? 0 : 1);

        int replace = 0;
        int mod0 = 0;
        int mod1 = 0;
        int mod2 = 0;

        // 统计连续段并计算替换次数
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            int len = j - i;
            if (len >= 3) {
                replace += len / 3;
                int mod = len % 3;
                if (mod == 0) {
                    mod0++;
                } else if (mod == 1) {
                    mod1++;
                } else {
                    mod2++;
                }
            }
            i = j;
        }

        if (n < 6) {
            return Math.max(missing, 6 - n);
        }

        if (n <= 20) {
            return Math.max(missing, replace);
        }

        int delete = n - 20;
        int remaining = delete;

        // 优先处理 len % 3 == 0 的段
        int use = Math.min(remaining, mod0);
        replace -= use;
        remaining -= use;

        // 再处理 len % 3 == 1 的段
        use = Math.min(remaining / 2, mod1);
        replace -= use;
        remaining -= use * 2;

        // 再处理 len % 3 == 2 的段
        use = Math.min(remaining / 3, mod2);
        replace -= use;
        remaining -= use * 3;

        // 剩余删除每 3 个可减少 1 次替换
        replace -= remaining / 3;

        return delete + Math.max(missing, replace);
    }
}

func strongPasswordChecker(s string) int {
	n := len(s)
	hasLower := false
	hasUpper := false
	hasDigit := false

	// 统计字符种类缺失
	for i := 0; i < n; i++ {
		ch := s[i]
		if ch >= 'a' && ch <= 'z' {
			hasLower = true
		} else if ch >= 'A' && ch <= 'Z' {
			hasUpper = true
		} else if ch >= '0' && ch <= '9' {
			hasDigit = true
		}
	}

	missing := 0
	if !hasLower {
		missing++
	}
	if !hasUpper {
		missing++
	}
	if !hasDigit {
		missing++
	}

	replace := 0
	mod0 := 0
	mod1 := 0
	mod2 := 0

	// 统计连续段并计算替换次数
	for i := 0; i < n; {
		j := i
		for j < n && s[j] == s[i] {
			j++
		}
		length := j - i
		if length >= 3 {
			replace += length / 3
			switch length % 3 {
			case 0:
				mod0++
			case 1:
				mod1++
			default:
				mod2++
			}
		}
		i = j
	}

	if n < 6 {
		if missing > 6-n {
			return missing
		}
		return 6 - n
	}

	if n <= 20 {
		if missing > replace {
			return missing
		}
		return replace
	}

	deleteCnt := n - 20
	remaining := deleteCnt

	// 优先处理 len % 3 == 0 的段
	use := remaining
	if use > mod0 {
		use = mod0
	}
	replace -= use
	remaining -= use

	// 再处理 len % 3 == 1 的段
	use = remaining / 2
	if use > mod1 {
		use = mod1
	}
	replace -= use
	remaining -= use * 2

	// 再处理 len % 3 == 2 的段
	use = remaining / 3
	if use > mod2 {
		use = mod2
	}
	replace -= use
	remaining -= use * 3

	// 剩余删除每 3 个可减少 1 次替换
	replace -= remaining / 3

	if missing > replace {
		return deleteCnt + missing
	}
	return deleteCnt + replace
}

相似题目

题目	难度	考察点
917. 仅仅反转字母	简单	字符串处理
520. 检测大写字母	简单	字符串检查
125. 验证回文串	简单	双指针
468. 验证IP地址	中等	字符串解析
14. 最长公共前缀	简单	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/58025671