[leetcode] 696. Count Binary Substrings

문제링크

https://leetcode.com/problems/count-binary-substrings/

input & output

Example 1

Input: s = "00110011"
Output: 6

• Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
  Notice that some of these substrings repeat and are counted the number of times they occur.
  Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2

Input: s = "10101"
Output: 4

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

---

Approach #1

/*
I : string
O : integer
C : 
    - 1 <= s.length <= 105
    - s[i] is either '0' or '1'.
E :



Input: s = "00110011"
                  ^
                   ^
Output: 6

0011
01
1100
10
0011
01

00110011
^


현재숫자랑 이전숫자를 비교해서 다르면 substr[cur]=1넣기
                       같으면 substr[cur]++;

if(s[cur]===0) substr[0]<=substr[1] res++
else if(s[cur]===1) substr[1]<=substr[0] res++


00110011
       ^
cur  0 1
     ---
0    1 0
0    2 0
1    2 1 -> 1(01)
1    2 2 -> 2(0011)
0    1 2 -> 3(10)
0    2 2 -> 4(1100)
1    2 1 -> 5(01)
1    2 2 -> 6(0011)

*/

Solution #1

var countBinarySubstrings = function(s) {
  let res=0;
  let preN=s[0];
  const substr=[0,0];
  for(let cur=0; cur<s.length; cur++){
      if(preN==s[cur]) substr[s[cur]]++;
      else substr[s[cur]]=1;
      preN=Number(s[cur]);
      //console.log(preN, substr);
      if(s[cur]==="0" && substr[0]<=substr[1]) res++;
      if(s[cur]==="1" && substr[1]<=substr[0]) res++;
  }
  return res;
};

Time Complexity

O(N)

N: s.length
s의 길이만큼 반복문을 돌며 substring이 조건에 가능한 string인지 확인하기 때문에 시간복잡도는 N.

Space Complexity

O(1)

substr 배열을 사용하긴 하지만 [0,0]으로 크기가 1인 배열에 값을 바꿔주며 사용하기 때문에 공간복잡도는 O(1)

---

Solution #2

var countBinarySubstrings = function (s) {
	s += "#";
    // prev=0의 개수, curr=1의 개수
	let curr = 1, prev = 0, count = 0;

	for (let i = 0; i < s.length - 1; i++){
		// 0 0 1 1 0 0 1 1
                //       ^
		// console.log(s[i - 1], s[i]);
		if (s[i + 1] === s[i]) curr++;
		else {
			count += Math.min(prev, curr);
			prev = curr;
			curr = 1;
		}
		// console.log(curr, prev);
		
	}
	return count;
};

Time Complexity

O(N)

N: s.length
s의 길이만큼 반복문을 돌며 substring이 조건에 가능한 string인지 확인하기 때문에 시간복잡도는 N.

Space Complexity

O(1)

curr, prev, count 변수만을 이용해 답을 산출해내기 때문에 공간복잡도는 O(1).

---