LeetCode 1525. Number of Good Ways to Split a String - Interview Prep Ep 84

⭐ Support my channel and connect with me:

Algorithm explained:
We can maintain two sliding windows, one for the distinct characters count on the left substring, the other for the right.
Whenever we move the pointer from the left to the right, we decrement the corresponding character count in the right window by one and we increment it in the left substring's window by one. Then we check if the distinct character counts equal, if so, we add one to the final result.

Time: O(n)
Space: O(1)

// TOOLS THAT I USE:

// MY FAVORITE BOOKS:

My ENTIRE Programming Equipment and Computer Science Bookshelf:

And make sure you subscribe to my channel!

Your comments/thoughts/questions/advice will be greatly appreciated!

#leetcode #leetcode1525 #programming #datastructures
#Kahnsalgorithm #graphsearch #topologicalsorting #softwareengineering #leetcode #algorithms #coding #interview #SDE #SWE #SiliconValley

[henggaocai]

You are doing so well explaining the code. Keep up the good work!

[edwardteach]

What got me confused was incrementing the left and decrementing the right at the same time until I understood it this way.

Since we're building a left (p) and a right(q) sub strings, you can think of it as were adding a character and building our left substring (p), while decrementing a character from our already built right substring (q).

s = "aacaba" =

("a", "acaba")
left = 'a' since we got the 'a' from decrementing the right and we're slowly building up our left substring

Thanks! Code in Python:
class Solution(object):
def numSplits(self, s):
"""
:type s: str
:rtype: int
"""
count = 0
left = [0] * 26
right = [0] * 26
for i in range(len(s)):
right[ord(s[i])-ord('a')] += 1

def count_distinct(arr):
count = 0
for num in arr:
if num != 0:
count += 1
return count

for i in range(len(s)):
left[ord(s[i])-ord('a')] += 1
right[ord(s[i])-ord('a')] -= 1
if count_distinct(left) == count_distinct(right):
count += 1
return count

[siddharthgupta]

Hi sir, great job in explaining the concepts . I just request you to make leetcode videos on a daily basis

[CrystalSergeant]

great videos but horrible microphone :(

[sajramkisho]

Mr.Fisher Coder, it will be very helpful if u make a code "walkthrough"for leetcode sortlist strictly using bottom up merge sort approach O(1) i am waiting for ur

[ankitkumarmahato]

Using two hashmap can also do the job.

[SmoothCode]

Do python for leetcode. You'd get more viewers that way.

[isiscuriel]

Hi I really appreciate your explanation. I was wondering if you could elaborate on why the time complexity is O(n)? Is it because even though you loop through the left and right arrays it would be consider constant time b/c the arrays are a set size ?