This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #696 (Easy): Count Binary Substrings
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given a string
s, count the number of non-empty (contiguous) substrings that have the same number of0's and1's, and all the0's and all the1's in these substrings are grouped consecutively.Substrings that occur multiple times are counted the number of times they occur.
Examples:
Example 1: Input: "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: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
Constraints:
s.lengthwill be between1and50,000.swill only consist of "0" or "1" characters.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
Since the 0's and 1's have to be grouped consecutively, we only have to be concerned with the most recent two groups (curr, prev) at any time as we iterate through the input string (s). Since each addition to our answer (ans) must therefore be centered on the "edge" between the two groups, we should be able to count multiple increases to ans at the same time.
For example, if we find a group that is "0001111", then we know that we've found multiple answer counts centered on the "01". Each additional extra character on both sides will be an extra answer, which means that "0011" and "000111" are also answers. In other words, the number that we should add to ans is equal to min(zeros, ones), or 3 in this example.
So we can now iterate through s, keeping track of the curr and prev groups, and when we find the end of a group, we can calculate our addition to ans and then swap the two variables while resetting curr to 1.
Since we're going to be comparing s[i] to s[i-1] to see if the character has changed, we'll need to start our iteration with i = 1 which means we should define a starting value for curr of 1. Also, since the end of s is technically the end of a group, we should add another min(curr, prev) onto ans before we return ans, as it won't be accounted for in the iteration through s.
- Time Complexity: O(N) where N is the length of s
- Space Complexity: O(1)
Implementation:
There are only minor differences in the code for all four languages.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var countBinarySubstrings = function(s) {
let curr = 1, prev = 0, ans = 0
for (let i = 1; i < s.length; i++)
if (s[i] === s[i-1]) curr++
else ans += Math.min(curr, prev), prev = curr, curr = 1
return ans + Math.min(curr, prev)
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def countBinarySubstrings(self, s: str) -> int:
curr, prev, ans = 1, 0, 0
for i in range(1, len(s)):
if s[i] == s[i-1]: curr += 1
else:
ans += min(curr, prev)
prev, curr = curr, 1
return ans + min(curr, prev)
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public int countBinarySubstrings(String s) {
int curr = 1, prev = 0, ans = 0;
for (int i = 1; i < s.length(); i++)
if (s.charAt(i) == s.charAt(i-1)) curr++;
else {
ans += Math.min(curr, prev);
prev = curr;
curr = 1;
}
return ans + Math.min(curr, prev);
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int countBinarySubstrings(string s) {
int curr = 1, prev = 0, ans = 0;
for (int i = 1; i < s.length(); i++)
if (s[i] == s[i-1]) curr++;
else ans += min(curr, prev), prev = curr, curr = 1;
return ans + min(curr, prev);
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-04-23T08:06:20+00:00) Solution: Count Binary Substrings. Retrieved from https://www.scien.cx/2021/04/23/solution-count-binary-substrings/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.