건물을 선택하는 방법의 수

거리를 따라 있는 건물의 유형을 나타내는 0-인덱스 이진 문자열s이 제공됩니다.

s[i] = '0'는 ith 건물이 사무실임을 나타내고

s[i] = '1'는 ith 건물이 레스토랑임을 나타냅니다.

시 공무원으로서 임의 검사를 위해 3개의 건물을 선택하려고 합니다. 그러나 다양성을 보장하기 위해 선택한 건물 중 두 개의 연속 건물이 같은 유형일 수 없습니다.

예를 들어, 주어진 s = "0**0**1**1**0**1**" 에서 1st , 3rd 및 5th 건물을 선택할 수 없습니다. 이는 동일한 유형의 두 개의 연속 건물로 인해 허용되지 않는 "0**11**" 건물입니다.

3개의 건물을 선택하는 유효한 방법의 수를 반환합니다.

예 1:

입력: s = "001101"
출력: 6
설명:
선택한 다음 인덱스 세트가 유효합니다.

[0,2,4] "00*110*1"에서 "010"을 형성

[0,3,4] "001*10*1"에서 "010"을 형성합니다

[1,2,4] "0*0110*1"에서 "010"을 형성

[1,3,4] "0*0110*1"에서 "010"을 형성합니다

[2,4,5] "00*1101*"에서 "101"을 형성합니다

[3,4,5] "001*101*"에서 "101"을 형성
다른 선택은 유효하지 않습니다. 따라서 총 6가지 방법이 있습니다.

예 2:

입력: s = "11100"
출력: 0
설명: 유효한 선택 항목이 없다고 표시될 수 있습니다.

제약:

3 <= s.length <= 105

s[i]는 '0' 또는 '1' 입니다.

해결책:

class Solution:
    def numberOfWays(self, s: str) -> int:
        n = len(s)
        z = 0
        o = 0
        zeroes = [z]
        ones = [o]
        for c in s:
            if c == '0':
                z += 1
            if c == '1':
                o += 1
            zeroes.append(z)
            ones.append(o)
        ways = 0
        for i in range(n):
            if s[i] == '0':
                ways += (ones[i] - ones[0]) * (ones[-1] - ones[i + 1])
            elif s[i] == '1':
                ways += (zeroes[i] - zeroes[0]) * (zeroes[-1] - zeroes[i + 1])
        return ways