A digital art gallery has an art collection which is represented as a binary string. Each digit in the string represents an artwork and there are two types of artworks: '0' represents a traditional artwork, '1' represents a modern artwork. Your task is to find out the number of ways to choose three artworks in ascending order of their position in the collection, such that no two adjacent selected artworks are of the same type.
Example:
collection = '01001'
The following sequences of artworks match the criterion:
- [1, 2, 3], that is, 01001 → 010
- [1, 2, 4], that is, 01001 → 010
- [2, 3, 5], that is, 01001 → 101
- [2, 4, 5], that is, 01001 → 101
The answer is 4.
Function Description:
Complete the function countWays in the editor below.
countWays has the following parameter:
string collection: a string that represents the collection
Returns:
long: the total number of ways to select 3 artworks that meet the criterion
Constraints:
- 1 ≤ |collection| ≤ 2×10⁵
- Each character in collection is either '0' or '1'
Input Format For Custom Testing
Sample Case 0
Sample Input For Custom Testing
STDIN:
10111
Sample Output:
collection = "10111"
Explanation:
The following sequences of artworks match the criterion:
- [1, 2, 3], that is, 10111 → 101
- [1, 2, 4], that is, 10111 → 101
- [1, 2, 5], that is, 10111 → 101
Asked in: DESHAW
Image of the Question
All Testcases Passed ✔
