Counting Binary Substrings (Backend)
Updated
Problem statement
A substring is a group of contiguous characters in a string. For instance, all substrings of abc are [a, b, c, ab, bc, abc].
Given a binary representation of a number, determine the total number of substrings present that match the following conditions:
- The 0s and 1s are grouped consecutively (e.g., 01, 10, 0011, 1100, 000111, etc.).
- The number of 0s in the substring is equal to the number of 1s in the substring.
As an example, consider the string 001101. The 4 substrings matching the two conditions include [0011, 01, 10, 01]. Note that 01 appears twice, from indices 1-2 and 4-5. There are other substrings, e.g. 001 and 011 that match the first condition but not the second.
Function
counting(s: String) → int
Complete the function counting in the editor 🐸👉.
Returns
int: the number of substrings of s that satisfy the two conditions
Examples
Example 1
s = "00110"return = 3No explanation for now...
Constraints
5 ≤ |s| ≤ 5 x 105each s[i] is either '0' or '1'
More Canva interview questions
Similar questions at other companies
- String CompressionAbridge · OAAbridge interview questions
- K Smallest SubstringAkuna Capital · OAAkuna Capital interview questions
- Format TextTikTok · OATikTok interview questions
- Next Greater Element IIIThe Walt Disney Company · OAThe Walt Disney Company interview questions
- Shortest SubstringRippling · OARippling interview questions
- Minimum Swaps to Make PalindromeAmazon · OA
- Longest Subsequence That Is a SubstringExpedia · OAExpedia interview questions
- Palindrome WordEpic · OAEpic interview questions
- String Search (Also for Core/Database Engineering)Snowflake · OASnowflake interview questions
- Count SubstringsSalesforce · OASalesforce interview questions