Hard

题目描述

如果一个密码满足下述所有条件，则认为这个密码是强密码：

  • 由至少 6 个，至多 20 个字符组成。
  • 至少包含一个小写字母，一个大写字母，和一个数字。
  • 不能包含三个连续相同的字符（比如 “Baaabb0” 是弱密码，但是 “Baaba0” 是强密码）。

给你一个字符串 password，返回将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0。

在一步中，你可以：

  • 插入一个字符到 password，
  • 从 password 中删除一个字符，或
  • 用另一个字符来替换 password 中的一个字符。

示例 1：

输入：password = "a"
输出：5

示例 2：

输入：password = "aA1"
输出：3

示例 3：

输入：password = "1337C0d3"
输出：0

提示：

  • 1 <= password.length <= 50
  • password 由字母、数字、点 '.' 或者感叹号 '!' 组成

解题思路

这道题需要分情况讨论，根据密码长度进行处理：

1. 长度不足 6 的情况：

  • 需要插入字符来达到最小长度要求
  • 插入的字符可以同时解决字符类型缺失和连续字符问题
  • 最少操作次数为 max(6 - n, missing_types)

2. 长度在 6-20 之间：

  • 只需要替换操作
  • 统计连续相同字符段，每 3 个字符需要 1 次替换
  • 替换操作可以同时解决字符类型缺失问题

3. 长度超过 20 的情况：

  • 优先删除多余字符
  • 智能删除：优先删除连续字符段中能最大化减少替换次数的字符
  • 对于长度为 k 的连续段，删除 k%3 个字符可以减少 1 次替换

核心思路是贪心算法，通过合理安排操作顺序来最小化总操作次数。对于连续字符的处理，我们使用优先队列来优化删除策略。

代码实现

class Solution {
public:
    int strongPasswordChecker(string password) {
        int n = password.length();
        bool hasLower = false, hasUpper = false, hasDigit = false;
        
        // 检查字符类型
        for (char c : password) {
            if (c >= 'a' && c <= 'z') hasLower = true;
            else if (c >= 'A' && c <= 'Z') hasUpper = true;
            else if (c >= '0' && c <= '9') hasDigit = true;
        }
        
        int missingTypes = (!hasLower) + (!hasUpper) + (!hasDigit);
        
        // 统计连续字符段
        vector<int> repeats;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && password[j] == password[i]) j++;
            if (j - i >= 3) {
                repeats.push_back(j - i);
            }
            i = j;
        }
        
        // 情况1: 长度 < 6
        if (n < 6) {
            return max(6 - n, missingTypes);
        }
        
        // 情况2: 长度 6-20
        if (n <= 20) {
            int replaces = 0;
            for (int len : repeats) {
                replaces += len / 3;
            }
            return max(replaces, missingTypes);
        }
        
        // 情况3: 长度 > 20
        int deleteCount = n - 20;
        int replaces = 0;
        
        // 优先删除能减少最多替换的字符
        // 按 len % 3 分组处理
        vector<vector<int>> groups(3);
        for (int len : repeats) {
            groups[len % 3].push_back(len);
        }
        
        // 先删除 len % 3 == 0 的段
        for (int& len : groups[0]) {
            if (deleteCount > 0) {
                int del = min(deleteCount, len - 2);
                deleteCount -= del;
                len -= del;
            }
        }
        
        // 再删除 len % 3 == 1 的段
        for (int& len : groups[1]) {
            if (deleteCount > 0) {
                int del = min(deleteCount, len - 2);
                deleteCount -= del;
                len -= del;
            }
        }
        
        // 最后删除 len % 3 == 2 的段
        for (int& len : groups[2]) {
            if (deleteCount > 0) {
                int del = min(deleteCount, len - 2);
                deleteCount -= del;
                len -= del;
            }
        }
        
        // 计算剩余的替换次数
        for (auto& group : groups) {
            for (int len : group) {
                if (len >= 3) replaces += len / 3;
            }
        }
        
        return (n - 20) + max(replaces, missingTypes);
    }
};

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        n = len(password)
        has_lower = any(c.islower() for c in password)
        has_upper = any(c.isupper() for c in password)
        has_digit = any(c.isdigit() for c in password)
        
        missing_types = sum([not has_lower, not has_upper, not has_digit])
        
        # 统计连续字符段
        repeats = []
        i = 0
        while i < n:
            j = i
            while j < n and password[j] == password[i]:
                j += 1
            if j - i >= 3:
                repeats.append(j - i)
            i = j
        
        # 情况1: 长度 < 6
        if n < 6:
            return max(6 - n, missing_types)
        
        # 情况2: 长度 6-20
        if n <= 20:
            replaces = sum(length // 3 for length in repeats)
            return max(replaces, missing_types)
        
        # 情况3: 长度 > 20
        delete_count = n - 20
        replaces = 0
        
        # 按 len % 3 分组处理
        groups = [[], [], []]
        for length in repeats:
            groups[length % 3].append(length)
        
        # 优先删除能减少最多替换的字符
        for mod in range(3):
            for i in range(len(groups[mod])):
                if delete_count > 0:
                    delete = min(delete_count, groups[mod][i] - 2)
                    delete_count -= delete
                    groups[mod][i] -= delete
        
        # 计算剩余的替换次数
        for group in groups:
            for length in group:
                if length >= 3:
                    replaces += length // 3
        
        return (n - 20) + max(replaces, missing_types)

public class Solution {
    public int StrongPasswordChecker(string password) {
        int n = password.Length;
        bool hasLower = false, hasUpper = false, hasDigit = false;
        
        foreach (char c in password) {
            if (c >= 'a' && c <= 'z') hasLower = true;
            else if (c >= 'A' && c <= 'Z') hasUpper = true;
            else if (c >= '0' && c <= '9') hasDigit = true;
        }
        
        int missingTypes = (hasLower ? 0 : 1) + (hasUpper ? 0 : 1) + (hasDigit ? 0 : 1);
        
        // 统计连续字符段
        List<int> repeats = new List<int>();
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && password[j] == password[i]) j++;
            if (j - i >= 3) {
                repeats.Add(j - i);
            }
            i = j;
        }
        
        // 情况1: 长度 < 6
        if (n < 6) {
            return Math.Max(6 - n, missingTypes);
        }
        
        // 情况2: 长度 6-20
        if (n <= 20) {
            int replaces = 0;
            foreach (int len in repeats) {
                replaces += len / 3;
            }
            return Math.Max(replaces, missingTypes);
        }
        
        // 情况3: 长度 > 20
        int deleteCount = n - 20;
        int totalReplaces = 0;
        
        // 按 len % 3 分组处理
        List<List<int>> groups = new List<List<int>> {
            new List<int>(), new List<int>(), new List<int>()
        };
        
        foreach (int len in repeats) {
            groups[len % 3].Add(len);
        }
        
        // 优先删除能减少最多替换的字符
        for (int mod = 0; mod < 3; mod++) {
            for (int k = 0; k < groups[mod].Count; k++) {
                if (deleteCount > 0) {
                    int del = Math.Min(deleteCount, groups[mod][k] - 2);
                    deleteCount -= del;
                    groups[mod][k] -= del;
                }
            }
        }
        
        // 计算剩余的替换次数
        foreach (var group in groups) {
            foreach (int len in group) {
                if (len >= 3) totalReplaces += len / 3;
            }
        }
        
        return (n - 20) + Math.Max(totalReplaces, missingTypes);
    }
}

var strongPasswordChecker = function(password) {
    const n = password.length;
    let hasLower = false, hasUpper = false, hasDigit = false;
    
    for (const c of password) {
        if (c >= 'a' && c <= 'z') hasLower = true;
        else if (c >= 'A' && c <= 'Z') hasUpper = true;
        else if (c >= '0' && c <= '9') hasDigit = true;
    }
    
    const missingTypes = (!hasLower ? 1 : 0) + (!hasUpper ? 1 : 0) + (!hasDigit ? 1 : 0);
    
    // 统计连续字符段
    const repeats = [];
    let i = 0;
    while (i < n) {
        let j = i;
        while (j < n && password[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
整体算法O(n)O(n)
  • 时间复杂度：O(n)，其中 n 是密码长度。需要遍历密码字符串统计字符类型和连续字符段
  • 空间复杂度：O(n)，最坏情况下需要存储所有连续字符段的长度信息

相关题目