【滑动窗口】LeetCode2953:统计完全子字符串

作者推荐

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

本题其它解法

【离散差分】LeetCode2953:统计完全子字符串

题目

给你一个字符串 word 和一个整数 k 。
如果 word 的一个子字符串 s 满足以下条件，我们称它是完全字符串：
s 中每个字符恰好出现 k 次。
相邻字符在字母表中的顺序至多相差 2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差至多为 2 。
请你返回 word 中完全子字符串的数目。
子字符串指的是一个字符串中一段连续非空的字符序列。
示例 1：
输入：word = “igigee”, k = 2
输出：3
解释：完全子字符串需要满足每个字符恰好出现 2 次，且相邻字符相差至多为 2 ：igigee, igigee, igigee 。
示例 2：
输入：word = “aaabbbccc”, k = 3
输出：6
解释：完全子字符串需要满足每个字符恰好出现 3 次，且相邻字符相差至多为 2 ：aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。
参数范围：
1 <= word.length <= 10⁵
word 只包含小写英文字母。
1 <= k <= word.length

滑动窗口

周赛的时候，忽略了：完全子字符串的长度是k的1到26倍。

时间复杂度

O(nmm)。n是字符串的长度，m的字符种类，也就是26。枚举字符结尾：O(n)；枚举窗口长度:O(m);统计合法字符数量O(m)。

变量解析


m_aCharNums	iWindowWidth个字符，各字母的数量

代码

核心代码

class Solution {
public:
int countCompleteSubstrings(string word, int k) {
m_iK = k;
int pre = 0;
int iRet = 0;
for (int i = 0; i < word.length(); i++)
{
if (i && (abs(word[i] - word[i - 1]) > 2))
{
iRet += Do(word.data()+pre, i - pre);
pre = i;
}
}
iRet += Do(word.data() + pre, word.length() - pre);
return iRet;
}
int Do(const char* p ,int len)
{
int iRet = 0;
auto AddNum = &
{
for (int i = 0; i < 26; i++)
{
if ((0 != m_aCharNums[i]) && (m_iK != m_aCharNums[i]))
{
return;
}
}
iRet++;
};
int iWindowWidth = 0;
for (int i = 1; (i <= 26)&&((iWindowWidth=m_iK*i)<= len); i++)
{
memset(m_aCharNums, 0, sizeof(m_aCharNums));
int j = 0;
for (; j < iWindowWidth; j++)
{
m_aCharNums[p[j] - ‘a’]++;
}
AddNum();
for (;j < len; j++)
{
m_aCharNums[p[j] - ‘a’]++;
m_aCharNums[p[j - iWindowWidth] - ‘a’]–;
AddNum();
}
}
return iRet;
}
int m_aCharNums[26];
int m_iK;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
string s;
int k, res;
{
Solution slu;
s = “ba”;
k = 1;
auto res = slu.countCompleteSubstrings(s, k);
Assert(3, res);
}
{
Solution slu;
s = “gvgvvgv”;
k = 2;
auto res = slu.countCompleteSubstrings(s, k);
Assert(1, res);
}
{
Solution slu;
s = “igigee”;
k = 2;
auto res = slu.countCompleteSubstrings(s, k);
Assert(3, res);
}
{
Solution slu;
s = “aaabbbccc”;
k = 3;
auto res = slu.countCompleteSubstrings(s, k);
Assert(6, res);
}

//CConsole::Out(res);

}

优化

不用每次都判断无法字符的数量，只会修改两个字符的数量，只判断这两个字符就可以了。

时间复杂度

O(nm)。

代码

class Solution {
public:
	int countCompleteSubstrings(string word, int k) {
		m_iK = k;
		int pre = 0;
		int iRet = 0;
		for (int i = 0; i < word.length(); i++)
		{
			if (i && (abs(word[i] - word[i - 1]) > 2))
			{
				iRet += Do(word.data()+pre, i - pre);
				pre = i;
			}
		}
		iRet += Do(word.data() + pre, word.length() - pre);
		return iRet;
	}
	int Do(const char* p ,int len)
	{
		int iRet = 0;		
		int iWindowWidth = 0;
		for (int i = 1; (i <= 26)&&((iWindowWidth=m_iK*i)<= len); i++)
		{
			memset(m_aCharNums,  0, sizeof(m_aCharNums));
			int j = 0;
			for (; j < iWindowWidth; j++)
			{
				m_aCharNums[p[j] - 'a']++;
			}
			int iVilidCount = std::count(m_aCharNums, m_aCharNums + 26, 0) + std::count(m_aCharNums, m_aCharNums + 26, m_iK);
			if (26 == iVilidCount)
			{
				iRet++;
			}
			auto Change = [&](int index, int iAdd)
			{
				bool bOld = (0 == m_aCharNums[index]) || (m_iK == m_aCharNums[index]);
				m_aCharNums[index] += iAdd;
				bool bNew = (0 == m_aCharNums[index]) || (m_iK == m_aCharNums[index]);
				iVilidCount += (int)bNew - (int)bOld;
			};
			for (;j < len; j++)
			{
				Change(p[j] - 'a',1);
				Change(p[j - iWindowWidth] - 'a', -1);
				iRet += (26 == iVilidCount);
			}
		}
		return iRet;
	}
	int m_aCharNums[26];
	int m_iK;
};