Python에서 각 방향이 분기별로 발생하도록 방향 문자열의 균형을 맞추는 프로그램

<시간/>

북쪽, 남쪽, 서쪽 및 동쪽에 대해 각각 "N", "S", "W" 및 "E"의 네 방향을 가진 문자열이 있다고 가정합니다. 네 방향이 각각 n/4번 발생하도록 업데이트할 수 있는 가장 짧은 부분 문자열의 크기를 찾아야 합니다. 여기서 n은 문자열 s의 크기입니다.

따라서 입력이 s ="NNSWWESN"과 같으면 출력은 1이 되고 여기서 n은 8이므로 8/4는 2이므로 마지막 N을 E로 변경하면 모든 방향이 두 번 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=s의 크기
n이 0이면
- 0을 반환
1/4 :=(n / 4)의 층
count :=s에 있는 각 요소의 빈도를 포함하는 목록
대상 :=새 지도
count의 각 쌍(dir, cnt)에 대해 do
- cnt> 분기이면
  - 대상[dir] :=분기 - cnt
대상이 비어 있으면
- 0을 반환
왼쪽 :=0
min_len :=정보
s의 각 인덱스 오른쪽 및 방향 dir에 대해 다음을 수행합니다.
- dir이 대상에 있으면
  - 대상[디렉터리] :=대상[디렉터리] + 1
- 대상의 모든 값 목록의 최소값>=0, do
  - min_len :=min_len의 최소값 및 (오른쪽 - 왼쪽 + 1)
  - 대상에 s[left]이면
    - 대상[s[left]] :=target[s[left]] - 1
    - 왼쪽 :=왼쪽 + 1
반환 min_len

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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"