Teaching Kids Programming – Split String with Same Distinct Counts (Sliding Window)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a lowercase alphabet string s. Return the number of ways to split the string into two strings such that the number of distinct characters in each string is the same.

Constraints
1 ≤ n ≤ 100,000 where n is the length of s
Example 1
Input
s = “abaab”
Output
2
Explanation
We can split it by “ab” + “aab” and “aba” + “ab”

for each index i split (0, i) and (i + 1, n – 1)
add +1 if both split contain equal distinct character.
try checking from left and based on that check from right

Split String with Same Distinct Counts (Sliding Window)

There are O(N) splits/partitions we can try each one. For each partition, we can count the number of distinct characters using a hash table e.g. Counter object in Python. This requires O(N^2) time overall.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def splitStringWithDistinctCount(self, s):
        if not s:
            return 0
        ans = 0
        for i in range(len(s)):
            c1 = Counter(s[:i+1])
            c2 = Counter(s[i+1:])
            if len(c1) == len(c2):
                ans += 1
        return ans

class Solution:
    def splitStringWithDistinctCount(self, s):
        if not s:
            return 0
        ans = 0
        for i in range(len(s)):
            c1 = Counter(s[:i+1])
            c2 = Counter(s[i+1:])
            if len(c1) == len(c2):
                ans += 1
        return ans

We can keep two hash maps and then when we move the partition point one position to the right, we can update the left hash map and right hash map accordingly. The time complexity is O(N) as updating a hash map with a key entry is O(1) constant.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def splitStringWithDistinctCount(self, s):
        if not s:
            return 0
        c1 = Counter()
        c2 = Counter(s)
        ans = 0
        for i in range(len(s)):
            c1[s[i]] += 1
            c2[s[i]] -= 1
            if c2[s[i]] == 0:
                del c2[s[i]]
            if len(c1) == len(c2):
                ans += 1
        return ans

class Solution:
    def splitStringWithDistinctCount(self, s):
        if not s:
            return 0
        c1 = Counter()
        c2 = Counter(s)
        ans = 0
        for i in range(len(s)):
            c1[s[i]] += 1
            c2[s[i]] -= 1
            if c2[s[i]] == 0:
                del c2[s[i]]
            if len(c1) == len(c2):
                ans += 1
        return ans

The space complexity for both implementations are O(N) because of the hash maps used to store the occurences of the characters.

–EOF (The Ultimate Computing & Technology Blog) —