[LeetCode]Unique Letter String

这道题可以转化为求[i, j]范围内substring的unique char的个数。Brute Force的做法是枚举所有i和j，然后统计[i,j]内的unique char。时间复杂度O(n^3)，显然不可行。优化的做法是，我们统计所有在i处结尾的substring的unique char的数量。用另一个指针j从i处从右向左扫，一边统计unique char的数量即可，这样我们在O(n)的时间可以统计出所有以i结尾的substring的unique char的数量。总的时间复杂度为O(n^2)，空间复杂度为O(n)，但是仍然会TLE，代码如下：

	class Solution {
	public:
	int uniqueLetterString(string S) {
	int len = S.size();
	if(!len)return 0;
	const int MOD = 1000000007;
	vector<int> dp(len, 0);
	dp[0] = 1;
	for(int i = 1; i < len; ++i)
	{
	if(i > 1 && S[i] == S[i - 1] && S[i] == S[i - 2])
	{
	dp[i] = dp[i - 1];
	continue;
	}
	unordered_map<int, int> map;
	++map[S[i]];
	dp[i] = 1;
	int cnt = 1;
	for(int j = i - 1; j >= 0; --j)
	{
	if(map.size() == 26 && !cnt)break;
	if(map.find(S[j]) != map.end())
	{
	if(map[S[j]] == 1)--cnt;
	++map[S[j]];
	}
	else
	{
	++cnt;
	++map[S[j]];
	}
	dp[i] = (dp[i] + cnt) % MOD;
	}
	}
	int res = 0;
	for(const auto& i : dp)res = (res + i) % MOD;
	return res;
	}
	};

view raw Unique Letter String_n_square.cpp hosted with ❤ by GitHub

我们尝试寻找更效率的方法。因为题目说了输入的字符只有大写字母26种，如果我们改变思路统计每个字符分别在多少个substring中出现了一次，假设我们可以O(n)时间内完成这项工作，那么总的时间复杂度也仍然是O(n)。利用这个思路，我们记录每个字符在string s中出现的位置，假设s长度为10，a出现在[0, 5, 8]三处:

1. 所有只包含0处a的substring都满足条件，有5个, [0, 0-4]
2. 所有只包含5处a的substring都满足条件，有15个，[1-5, 5-7]
3. 所有只包含8处a的substring都满足条件，有6个，[6-8, 8-9]

对于每一种字符我们都统计一遍。时间复杂度，空间复杂度均为O(n)，代码如下：

	class Solution {
	public:
	int uniqueLetterString(string S) {
	int len = S.size();
	long long res = 0;
	if(!len)return 0;
	const int MOD = 1000000007;
	unordered_map<char, vector<int>> idxes;
	for(int i = 0; i < len; ++i)idxes[S[i]].push_back(i);
	for(auto& p : idxes)p.second.push_back(len);
	for(int i = 0; i < 26; ++i)
	{
	char c = 'A' + i;
	if(idxes.find(c) == idxes.end())continue;
	int prev = -1, next = -1;
	for(const int& idx : idxes[c])
	{
	if(next == -1)
	{
	next = idx;
	continue;
	}
	else
	{
	res += (next - prev) * (idx - next);
	prev = next;
	next = idx;
	}
	}
	}
	return res % MOD;
	}
	};

view raw Unique Letter String_n_1.cpp hosted with ❤ by GitHub

另一种官方给出的解法，思路是类似的，分别统计每个字符。假设idx(c)为字符c在string s中出现的位置，从小到大排列。我们用f[i]['a']表示在i处开头的substring只包含'a'一次的substring，显然f[i] = f[i]['a'] + f[i]['b'] + ... + f[i]['z']。比如idx('a') = [0, 5, 8]，f[0]['a'] = idx('a')[1] - idx('a')[0] = 5，对应[0, 0-4]。如果我们扫到i = 1，f[i]['a']会变，这时候f[1]['a'] = idx('a')[2] - idx('a')[1] = 3，对应[1, 5-7]。剩下的f[i]['b'] ... f[i]['z']并不会变。所以f[1] = f[0] + f[1]['a'] - f[0]['a']。所以我们从左向右扫，算出每个i对应的f[i]即可，我们可以用一个array arr[26]记录对应每个字符c在idx(c)中此时对应的位置，f[i][c] = idx(c)[arr[c - 'a'] + 1] - idx(c)[arr[c - 'a']]。时间复杂度O(n)，代码如下：

	class Solution {
	public:
	int uniqueLetterString(string S) {
	int len = S.size();
	long long curr = 0, res = 0;
	if(!len)return 0;
	const int MOD = 1000000007;
	unordered_map<char, vector<int>> idxes;
	vector<int> peek(len, 0);
	for(int i = 0; i < len; ++i)idxes[S[i]].push_back(i);
	for(auto& p : idxes)
	{
	p.second.push_back(len);
	curr += calculate(idxes, peek, p.first);
	}
	for(const auto& c : S)
	{
	res += curr;
	long long old = calculate(idxes, peek, c);
	++peek[c - 'A'];
	curr += calculate(idxes, peek, c) - old;
	}
	return res % MOD;
	}
	private:
	long long calculate(unordered_map<char, vector<int>>& idxes, vector<int>& peek, char c)
	{
	auto idx = idxes[c];
	int i = peek[c - 'A'];
	return i == idx.size() - 1? 0 : idx[i + 1] - idx[i];
	}
	};

view raw Unique Letter String_n_2.cpp hosted with ❤ by GitHub