Number of Good Ways to Split a String

Leetcode Problem 1525: Number of Good Ways to Split a String

Problem Summary

You are given a string s. A good split is a partition of s into two non-empty parts s = s1 + s2 such that the number of distinct letters in s1 equals the number of distinct letters in s2. Return the number of good splits.

Constraints:

• The string has between 1 and 100,000 characters, consisting of lowercase English letters only.

Techniques

• Hash Table
• String
• Dynamic Programming
• Bit Manipulation

Solution

function numSplits(s: string): number {
    let leftChars = new Map<string, number>()
    let rightChars = new Map<string, number>()
    let goodSplits = 0

    for (const char of s) {
        rightChars.set(char, (rightChars.get(char) || 0) + 1)
    }

    for (const char of s) {
        if (leftChars.size === rightChars.size) {
            goodSplits++
        }
        
        let countRight = rightChars.get(char) || 0

        if (countRight === 1) {
            rightChars.delete(char)
        } else {
            rightChars.set(char, --countRight)
        }

        leftChars.set(char, (leftChars.get(char) || 0) + 1)
    }

    return goodSplits
};

console.log(numSplits("aacaba"))