Skip to content

1573. Number of Ways to Split a String 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  int numWays(string s) {
    constexpr int kMod = 1'000'000'007;
    const int ones = count(s.begin(), s.end(), '1');
    if (ones % 3 != 0)
      return 0;
    if (ones == 0) {
      const long n = s.size();
      return (n - 1) * (n - 2) / 2 % kMod;
    }

    int s1End = -1;
    int s2Start = -1;
    int s2End = -1;
    int s3Start = -1;
    int onesSoFar = 0;

    for (int i = 0; i < s.length(); ++i) {
      if (s[i] == '1')
        ++onesSoFar;
      if (s1End == -1 && onesSoFar == ones / 3)
        s1End = i;
      else if (s2Start == -1 && onesSoFar == ones / 3 + 1)
        s2Start = i;
      if (s2End == -1 && onesSoFar == ones / 3 * 2)
        s2End = i;
      else if (s3Start == -1 && onesSoFar == ones / 3 * 2 + 1)
        s3Start = i;
    }

    return static_cast<long>(s2Start - s1End) * (s3Start - s2End) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
  public int numWays(String s) {
    final int kMod = 1_000_000_007;
    final int ones = (int) s.chars().filter(c -> c == '1').count();
    if (ones % 3 != 0)
      return 0;
    if (ones == 0) {
      final long n = s.length();
      return (int) ((n - 1) * (n - 2) / 2 % kMod);
    }

    int s1End = -1;
    int s2Start = -1;
    int s2End = -1;
    int s3Start = -1;
    int onesSoFar = 0;

    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == '1')
        ++onesSoFar;
      if (s1End == -1 && onesSoFar == ones / 3)
        s1End = i;
      else if (s2Start == -1 && onesSoFar == ones / 3 + 1)
        s2Start = i;
      if (s2End == -1 && onesSoFar == ones / 3 * 2)
        s2End = i;
      else if (s3Start == -1 && onesSoFar == ones / 3 * 2 + 1)
        s3Start = i;
    }

    return (int) ((long) (s2Start - s1End) * (s3Start - s2End) % kMod);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def numWays(self, s: str) -> int:
    kMod = 1_000_000_007
    ones = s.count('1')
    if ones % 3 != 0:
      return 0
    if ones == 0:
      n = len(s)
      return (n - 1) * (n - 2) // 2 % kMod

    s1End = -1
    s2Start = -1
    s2End = -1
    s3Start = -1
    onesSoFar = 0

    for i, c in enumerate(s):
      if c == '1':
        onesSoFar += 1
      if s1End == -1 and onesSoFar == ones // 3:
        s1End = i
      elif s2Start == -1 and onesSoFar == ones // 3 + 1:
        s2Start = i
      if s2End == -1 and onesSoFar == ones // 3 * 2:
        s2End = i
      elif s3Start == -1 and onesSoFar == ones // 3 * 2 + 1:
        s3Start = i

    return (s2Start - s1End) * (s3Start - s2End) % kMod