DEV Community

kevin074
kevin074

Posted on

Leetcode diary: 1525. Number of Good Ways to Split a String

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

I was thrown off by this question a bit, because it's supposed to be a medium difficulty and a DP question. It is not really either lol ...

Anyways, my thought process was like this:
1.) our goal is just to match left and right unique character number
2.) we can utilize sets to keep count of unique characters
3.) But that would not work for the right side, since we need to keep count of how many of each, when it reaches 0, we remove.
4.) so we'll just use a map to get the best of both worlds.
5.) now it's just a matter of splitting the string and iterate!

below is the actual code:

var numSplits = function(s) {
    const sSplit = s.split('');
    const leftSet = new Set();
    const rightMap = sSplit.reduce(function(map, letter){
        map[letter] = map[letter] ? map[letter]+1 : 1;
        return map;
    },{});

    let goodNum = 0;

    sSplit.forEach(function(letter){
        leftSet.add(letter);
        rightMap[letter]--;
        if(rightMap[letter] == 0) { delete rightMap[letter]; }

        if(leftSet.size === Object.keys(rightMap).length) {
            goodNum++;
        }
    });

    return goodNum;
};
Enter fullscreen mode Exit fullscreen mode

the performance is really good since it's just O(n), there seems to be no trickery to this since a couple of posts in the discussion are basically the same.

Let me know anything on your mind after reading through this, THANKS!

Top comments (0)