[LeetCode] Strong Password Checker

这道题比较麻烦，但是我们可以明确要分情况考虑：

1. 如果len < 6，我们只需要考虑insert和replace
2. 如果len >= 6 && len <= 20，我们只需要考虑replace
3. 如果len > 20，我们要考虑delete和replace

对于第一种情况，我们先考虑insert，insert就要insert 6 - len个字符，假设为了满足条件2我们需要insert或者replace k(k = 1/2)个新的字符种类，那么我们只需要max(6 - len, k)的步骤就可以满足所有条件。对于情况3，若连续子串长度为3或者4，我们直接插入一个字符就必定满足，而max(6 - len, k)肯定>= 1；对于长度为5的连续子串，我们插入一个字符无法使其满足条件3，但是注意条件2，其肯定还缺两种类型的字符，所以我们插入之后再replace一个，需要两步，2 = max(6 - 5, 2)。

对于第二种情况，我们只需要考虑replace，首先第一种条件已经满足。那么满足2的条件假设我们需要replace k(k = 1/2)个字符。为了满足条件3假设我们需要replace m个字符，那么对于一个长度为subLen的连续子串我们需要replace subLen / 3个字符使其满足条件，比如aaaaa我们只需要变成aabaa即可。那么我们只需要取max(k, m)即可。

对于第三种情况会有点复杂，因为delete也可以减少连续重复子串的数量，因为我们无论如何都需要删除len - 20个字符，所以我们先考虑delete的情况，那么我们如何delete呢。len % 3有0，1，2三种情况，由于replace的m个字符取决于len / 3，我们要尽量减少为了满足条件3而replace的m个字符，那么对于这三种情况，分别删除1，2，3个字符可以使m减少1。显然我们从len % 3 = 0的情况开始删一直到len % 3 = 2。当然我们要keep track of delete字符的数量，当期数量不足的时候我们停止。当处理完len % 3 =1 和2的情况的时候，所有剩下的连续重复子串的长度都为len % 3 = 2我们就看剩下的要删除的字符还能够将m减少多少，现在每减少一个m都需要删除3个字符。最后我们在考虑还有多少个字符需要replace来满足条件3和条件2，也就是max(k, m)，m为更新之后的m。

时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int strongPasswordChecker(string s) {
	//toReplace represent number of replace we can do to suffice case 3
	int len = s.size(), needLower = 1, needUpper = 1, needNum = 1, left = 0, toReplace = 0;
	//let say subLen is length of repeating chars with length more than 2
	//toReplace only depends on subLen / 3
	//So we use map to count subLen % 3 == 0, subLen % 3 == 1 and subLen % 3 == 2
	//when deleteing, we delete from subLen % 3 == 0 since it can reduce toReplace by deleting least characters
	vector<unordered_map<int, int>> counts(3);
	for(int i = 0; i <= len; ++i)
	{
	char c = s[i];
	if(islower(c))needLower = 0;
	if(isupper(c))needUpper = 0;
	if(isdigit(c))needNum = 0;
	if(i >= len || c != s[left])
	{
	int subLen = i - left;
	if(subLen >= 3)
	{
	++counts[subLen % 3][subLen];
	toReplace += subLen / 3;
	}
	left = i;
	}
	}
	if(len < 6)return max(6 - len, needUpper + needLower + needNum);
	else if(len <= 20)return max(toReplace, needUpper + needLower + needNum);
	else
	{
	//delete first, then replace
	int toDelete = len - 20, totalDeleted = toDelete;
	toReplace = 0;
	for(int i = 0; i < 3; ++i)
	{
	//first check deleting 1 char
	//then check deleting 2 and deleting 3
	for(auto&& p : counts[i])
	{
	if(i < 2)
	{
	int canDelete = min(p.second, toDelete / (i + 1));
	toDelete -= canDelete * (i + 1);
	p.second -= canDelete;
	//now three will be only len % 3 == 2
	if(p.first - (i + 1) > 2)counts[2][p.first - (i + 1)] += canDelete;
	}
	//now we have all repeating substring with len % 3 == 2, counting it
	toReplace += p.second * (p.first / 3);
	}
	}
	//if we have more char can delete, delete to reduce toReplace
	toReplace -= (toDelete / 3);
	return totalDeleted + max(toReplace, needUpper + needLower + needNum);
	}
	}
	};

view raw Strong Password Checker.cpp hosted with ❤ by GitHub