Skip to content

1525. Number of Good Ways to Split a String 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int numSplits(string s) {
    const int n = s.length();
    int ans = 0;
    // prefix[i] := the number of unique letters in s[0..i]
    vector<int> prefix(n);
    // suffix[i] := of unique letters in s[i..n)
    vector<int> suffix(n);
    unordered_set<int> seen;

    for (int i = 0; i < n; ++i) {
      seen.insert(s[i]);
      prefix[i] = seen.size();
    }

    seen.clear();

    for (int i = n - 1; i >= 0; --i) {
      seen.insert(s[i]);
      suffix[i] = seen.size();
    }

    for (int i = 0; i + 1 < n; ++i)
      if (prefix[i] == suffix[i + 1])
        ++ans;

    return ans;
  }
};

 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
class Solution {
  public int numSplits(String s) {
    final int n = s.length();
    int ans = 0;
    int[] prefix = new int[n];
    int[] suffix = new int[n];
    Set<Character> seen = new HashSet<>();

    for (int i = 0; i < n; ++i) {
      seen.add(s.charAt(i));
      prefix[i] = seen.size();
    }

    seen.clear();

    for (int i = n - 1; i >= 0; --i) {
      seen.add(s.charAt(i));
      suffix[i] = seen.size();
    }

    for (int i = 0; i + 1 < n; ++i)
      if (prefix[i] == suffix[i + 1])
        ++ans;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def numSplits(self, s: str) -> int:
    n = len(s)
    ans = 0
    seen = set()
    prefix = [0] * n
    suffix = [0] * n

    for i in range(n):
      seen.add(s[i])
      prefix[i] = len(seen)

    seen.clear()

    for i in reversed(range(n)):
      seen.add(s[i])
      suffix[i] = len(seen)

    for i in range(n - 1):
      if prefix[i] == suffix[i + 1]:
        ans += 1

    return ans