leetcode 5232. 替换子串得到平衡字符串

缘起

群里有人水者这道题目~ leetcode 5232. 替换子串得到平衡字符串

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

 

给你一个这样的字符串 s，请通过「替换子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

 

示例 1：

输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。
示例 2：

输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
示例 3：

输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。 
示例 4：

输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
 

提示：

1 <= s.length <= 10^5
s.length 是 4 的倍数
s 中只含有 'Q', 'W', 'E', 'R' 四种字符

ps: 对于本题, 要选出一个子串（连续字符）一次替换成功~, 而不能是不连续的.

思路是首先计算QWER四个字符的个数, 判断出不足n/4个字符的字符有哪些, 还差多少. 而哪些字符有多? 然后尺取. 看看哪一段满足这个诉求(即至少要提供多少个这个字符, 至少提供多少个那种字符…). 就行了. 复杂度是O(n)的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class Solution {
public:
	int balancedString(string s) 
	{
		int n = s.length();
		int ans = 1e+5;
		memset(cnt, 0, sizeof(cnt));
		memset(a, 0, sizeof(a));
		for (int i = 0;i<n; i++)
		{
			switch(s[i])
			{
			case 'Q':
				++cnt[0];
				break;
			case 'W':
				++cnt[1];
				break;
			case 'E':
				++cnt[2];
				break;
			case 'R':
				++cnt[3];
				break;
			}
		} // 统计四种字符各自多少个
		for (int i = 0;i<4;i++)
		{
			if (cnt[i]>n/4)
			{
				cnt[i] -= n/4; // i这个字符要提供cnt[i]-n/4个
			}
			else
			{
				cnt[i] = 0; // 不需要提供字符
			}
		}
		if (!cnt[0] && !cnt[1] &&!cnt[2] &&!cnt[3]) // 如果伊始就是平衡字符串
		{
			return 0;
		}
		int head = 0, tail = 0; // 尺取虫头尾
		while(head<n)
		{
			int idx = map2idx(s[head]); // 这是哪个字符
			if (cnt[idx]) // 如果是能提供字符的
			{
				++a[idx];
				if (ck()) // 如果能满足的话
				{
					while(tail<=head)
					{
						idx = map2idx(s[tail]);
						++tail;
						if (cnt[idx])
						{
							--a[idx];
						}
						if (!ck()) // 如果tail前移动了就不满足了
						{
							break;
						}
					}
					ans = min(ans, head-tail+2); // s[tail-1,...,head]就是满足的
				}
			}
			++head;
		}
		return ans;
	}

	int cnt[4],a[4]; // QWER四个字符的个数, 然后最后变成要提供出来的字符, a[0,1,2,3]分别是累计的Q,W,E,R字符数量.
	bool used[100005];
	int map2idx(char c) // 简单的映射
	{
		switch(c)
		{
		case 'Q':
			return 0;
		case 'W':
			return 1;
		case 'E':
			return 2;
		case 'R':
			return 3;
		}
		return -1;
	}

	bool ck() // 看看a是否满足了cnt的需求
	{
		for (int i = 0;i<4; i++)
		{
			if (cnt[i]>a[i])
			{
				return false;
			}
		}
		return true;
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
20 ms
, 在所有 cpp 提交中击败了
100.00%
的用户
内存消耗 :
10 MB
, 在所有 cpp 提交中击败了
100.00%
的用户