LeetCode: Number of Ways to Split a String Solution

Playing with indexes

Approach

Calculate number of ones and store their indexes

If number of ones is not divisible by 3, then the result is 0

If number of ones is 0, then the result is combination of string's length minus 1, taken 2

1000000
2
3string length of 6
4
5we have 5 possible position to place dividers, but we only need to place 2 dividers
6
7so the result will be the combination of 2-divider selected in 5 possibilities

In the normal case, the result will be the possibilities of placing dividers in the first and the last gaps

1s  =  1  0  0  1  0  0  0  1  0  1  0  0  1  1  0
2i  =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
3i1 =  0  _  _  3  _  _  _  7  _  9  _  _ 12 13  _
4
5to maintain size of the splits, we could place any dividers between 2 gaps:
6- (3,  7) - 4 possibilities
7- (9, 12) - 3 possibilities
8so the result will be 4 * 3 = 12

Implementation

1var numWays = function (s) {
2  const MOD = 1e9 + 7
3  const idxOfOnes = s
4    .split("")
5    .map((char, idx) => [char, idx])
6    .filter(([char, idx]) => char === "1")
7    .map(([char, idx]) => idx)
8
9  if (idxOfOnes.length % 3 !== 0) return 0
10  if (idxOfOnes.length === 0)
11    return (((s.length - 1) * (s.length - 2)) / 2) % MOD
12
13  const firstGapEnd = idxOfOnes.length / 3
14  const firstGapStart = firstGapEnd - 1
15  const secondGapEnd = firstGapEnd * 2
16  const secondGapStart = secondGapEnd - 1
17
18  return (
19    ((idxOfOnes[firstGapEnd] - idxOfOnes[firstGapStart]) *
20      (idxOfOnes[secondGapEnd] - idxOfOnes[secondGapStart])) %
21    MOD
22  )
23}