[Leetcode] 696. Count Binary Substrings

문제: leetcode.com/problems/count-binary-substrings/

 

DFS 끄적거리다가 못풀었다.

 

Easy인데..

 

착찹한 심정으로 Solution 해설이나 해본다. Solution은 Leetcode 사이트에 있다.

 

Intuition

We can convert the string s into an array groups that represents the length of same-character contiguous blocks within the string. For example, if s = "110001111000000", then groups = [2, 3, 4, 6].

For every binary string of the form '0' * k + '1' * k or '1' * k + '0' * k, the middle of this string must occur between two groups.

Let's try to count the number of valid binary strings between groups[i] and groups[i+1]. If we have groups[i] = 2, groups[i+1] = 3, then it represents either "00111" or "11000". We clearly can make min(groups[i], groups[i+1]) valid binary strings within this string. Because the binary digits to the left or right of this string must change at the boundary, our answer can never be larger.

Algorithm

Let's create groups as defined above. The first element of s belongs in it's own group. From then on, each element either doesn't match the previous element, so that it starts a new group of size 1; or it does match, so that the size of the most recent group increases by 1.
Afterwards, we will take the sum of min(groups[i-1], groups[i]).

 

문제풀이를 위한 직관

 

- String s 를 문자열 내에 동일한 연속 block의 길이를 나타내는 array 그룹으로 변환 가능하다.  

- 예를들어 s가 "110001111000000" 인 경우, group은  [2, 3, 4, 6]이될것이다.

- 모든 binary string은  '0' * k + '1' * k or '1' * k + '0' * k 의 형태로 나타단다. 중간 그룹은 반드시 2 그룹 이내일 것이다.

- groups[i]와 groups[i+1] 사이의 유효한 binary string을 count 해 보자. groups[i] =2 , groups[i+1] =3 을 가지게 되는 경우, 이는 "00111" 또는 "11000"을 의미하게 될 것이다. 우리는 여기서 min( groups[i], groups[i+1] ) valid binary string을 만들어 낼 수 있다.  --> 왼쪽 또는 오른쪽에 있는 binary 숫자가 반드시 경계를 이루고, 우리가 원하는 답을 바꾸지 않는다. ( 더 크게 만들지 않는다. )

 

알고리즘

 

- String s 의 첫 항목은 group에 들어간다. 그로부터,  이전항목과 match되지 않으면 size 1부터 그룹을 시작, 매치되는 항목은 size를 계속 1씩 증가시켜 나간다.

- 알고리즘을 수행후 우리는 group의 최소값들의 합을 답으로 택할 것이다.

 

사실 읽어도 뭔 소린가 싶긴 하다.

group [2, 3, 4, 6] 예시를 계산해보면.. 답이 9가 나와야 하는데..

min ( 2, 3 ) + min ( 3, 4 ) + min ( 4, 6 ) = 2 + 3 + 4= 9 가 답이라는 얘기다.

 

 

다시 문제의 예시로 돌아가보자..

Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

10, 01, 10, 01 이 sub string 후보가 되어 답이 4가 나온다.

알고리즘 대로라면, 

[1, 1, 1, 1, 1] 그룹이 되고, 이를 계산하면 min( 1, 1 ) + min (1, 1) + min (1, 1) + min( 1, 1 ) = 4가 나온다.

 

이쯤 보니 직관 항목에서 4번째 요소가 가장 중요한 개념으로 보이는데, 2개의 그룹을 비교했을때 0, 과 1로 구분됨을 보장하고 여기서 그룹개수의 최소 개를 구하는 것이 substring 개수와 동일하다는 것을 말해주는 것으로 보인다.

 

계속 보다보면 이해가 될 것 같지만.. 경험이 있어야 생각 날 것 같은 문제로 보인다.