题目:
题解:
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))int strongPasswordChecker(char * password) {int n = strlen(password);bool has_lower = false, has_upper = false, has_digit = false;for (int i = 0; i < n; i++) {if (islower(password[i])) {has_lower = true;} else if (isupper(password[i])) {has_upper = true;} else if (isdigit(password[i])) {has_digit = true;}}int categories = has_lower + has_upper + has_digit;if (n < 6) {return MAX(6 - n, 3 - categories);} else if (n <= 20) {int replace = 0;int cnt = 0;char cur = '#';for (int i = 0; i < n; i++) {if (password[i] == cur) {++cnt;} else {replace += cnt / 3;cnt = 1;cur = password[i];}}replace += cnt / 3;return MAX(replace, 3 - categories);} else {// 替换次数和删除次数int replace = 0, remove = n - 20;// k mod 3 = 1 的组数,即删除 2 个字符可以减少 1 次替换操作int rm2 = 0;int cnt = 0;char cur = '#';for (int i = 0; i < n; i++) {if (password[i] == cur) {++cnt;} else {if (remove > 0 && cnt >= 3) {if (cnt % 3 == 0) {// 如果是 k % 3 = 0 的组,那么优先删除 1 个字符,减少 1 次替换操作--remove;--replace;} else if (cnt % 3 == 1) {// 如果是 k % 3 = 1 的组,那么存下来备用++rm2;}// k % 3 = 2 的组无需显式考虑}replace += cnt / 3;cnt = 1;cur = password[i];}}if (remove > 0 && cnt >= 3) {if (cnt % 3 == 0) {--remove;--replace;} else if (cnt % 3 == 1) {++rm2;}}replace += cnt / 3;// 使用 k % 3 = 1 的组的数量,由剩余的替换次数、组数和剩余的删除次数共同决定int use2 = MIN(MIN(replace, rm2), remove / 2);replace -= use2;remove -= use2 * 2;// 由于每有一次替换次数就一定有 3 个连续相同的字符(k / 3 决定),因此这里可以直接计算出使用 k % 3 = 2 的组的数量int use3 = MIN(replace, remove / 3);replace -= use3;remove -= use3 * 3;return (n - 20) + MAX(replace, 3 - categories);}
}