当以下条件都满足时，一个密码被视为是强密码： 至少包含 6 个字符，但不超过 20 个字符。 至少包含一个小写字母，一个大写字母，和一个数字。 不能包含三个连续的重复字符（"...aaa..."是弱密码，但"...aa...a..."是强密码，假设它们的其他条件都满足了）。 写一个函数 strongPasswordChecker(s)，它将一个字符串 s 作为输入，并且返回将其转换成强密码需要的最少改变次数。如果 s 已经是一个强密码了，返回 0 。 插入、删除或者替换任意一个字符都视为一次改变。
点这里在线做题
样例 1: 输入："aaa123" 输出：1 解释："aaa123"->"aaA123"
样例 2: 输入："a" 输出：5 解释："a"->"aa"->"aaA"->"aaA1"->"aaA12"->"aaA123"
[题解]
考点： 思维
题解：本题根据要求最小的改变次数，确定修改策略即可。
变为强密码需要解决三种问题： 长度小于 6 时需要插入字符，长度大于 20 时需要删除字符 缺失字符或数字，此时可以通过插入或者替换字符解决 出现三个及以上重复字符，利用置换解决该问题会更好，可以同时做到解决情况二和情况三。
接下来，按照长度进行讨论。 当长度小于 6 时，尽量采用插入操作，既可以增加长度也可以避免重复字符连续。 当长度大于等于 6 时，对于重复字符个数 k 大于等于 3 的情况，先将其删除到最近的(3m+2)个，那么如果 k 正好被 3 整除，那么我们直接变为 k-1，如果 k%3=1，那么变为 k-2 。这样做的好处是 3m+2 个重复字符可以用替换 m 个字符来去除重复，然后遍历一次，进行删除和替换，可以直接删除 3m 个，最少删除操作。 public class Solution { /** * @param s: a string * @return: return an integer */ public int strongPasswordChecker(String s) { // write your code here int res = 0, n = s.length(), lower = 1, upper = 1, digit = 1; int [] v = new int [n]; for (int i = 0; i < n;) { //遍历是否存在缺失字符种类 if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') { lower = 0; } if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') { upper = 0; } if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { digit = 0; } int j = i; while (i < n && s.charAt(i) == s.charAt(j)) { ++i; } v[j] = i - j; //标记 j 位置开始连续重复字符的数量 } int missing = (lower + upper + digit); //缺失的字符种类数 if (n < 6) { int diff = 6 - n; //缺失的长度 res += diff + Math.max(0, missing - diff); //缺失长度加上 missing - diff 差值(因为增加的字符不一定补全字符种类，替换) } else { int over = Math.max(n - 20, 0), left = 0; //超出长度 res += over; for (int k = 1; k < 3; ++k) { //如果重复数量 k%3==0，-1 达到 3m+2 。如果 k%3==1，-2 达到 3m+2 for (int i = 0; i < n && over > 0; ++i) { if (v[i] < 3 || v[i] % 3 != (k - 1)) { continue; } v[i] -= k; over -=k; //删除字符 } } for (int i = 0; i < n; ++i) { if (v[i] >= 3 && over > 0) { int need = v[i] - 2; //通过-2 得到 3m v[i] -= over; over -= need; //直接选择删除 3m 个 } if (v[i] >= 3) { //如果 v[i]>=3 那么需要进行替换操作 left += v[i] / 3; } } res += Math.max(missing, left); //每次除以 3 即为替换的字符个数 } return res; } }
更多题解戳这里