用于平衡方向字符串的程序,以便每个方向在 Python 中出现四分之一次
假设我们有一个字符串s,它有四个方向“N”、“S”、“W”和“E”,分别代表北、南、西和东。我们必须找到可以更新的最短子串的大小,使得四个方向中的每一个都出现n/4次,其中n是字符串s的大小。
所以,如果输入像s="NNSWWESN",那么输出将是1,这里n是8,所以8/4是2,所以如果我们把最后的N改成E,那么所有方向都会出现两次。
示例
让我们看看以下实现以获得更好的理解-
from collections import Counter
def solve(s):
n = len(s)
if not n:
return 0
quarter = n //4
count = Counter(s)
target = dict()
for (dir, cnt) in count.items():
if cnt > quarter:
target[dir] = quarter - cnt
if not target:
return 0
left, min_len = 0, float("inf")
for right, dir in enumerate(s):
if dir in target:
target[dir] += 1
while min(target.values()) >= 0:
min_len = min(min_len, right - left + 1)
if s[left] in target:
target[s[left]] -= 1
left += 1
return min_len
s = "NNSWWESN"
print(solve(s))输入
"NNSWWESN"输出结果
1
热门推荐
1 狗狗技能训练
5 如何训练狗狗笑
6 狗狗训练排便
9 狗狗响片训练
10 如何训练狗狗不捡食
11 狗狗尿训练
12 怎么训练狗狗找东西
13 狗狗训练站立
14 狗狗训练飞盘
15 鞍山狗狗训练
16 怎样训练泰迪狗狗谢谢
17 狗狗外出训练
18 怎么训练金毛狗狗大小便