用于平衡方向字符串的程序,以便每个方向在 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