Search code examples
pythonrecursiondivide-and-conquer

longestSubstring python solution what does it mean --> for t in s.split(c)

I have been studying leetCode and I ran into this problem: Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

The most elegant solution so far is below but I don't understand

A: What is it trying to do

for t in s.split(c)

First marching through a set version of string

Then, taking the original s (NON-set, or list s with duplicates), splitting s where the character whose frequency is less than k? Then taking one substring at a time? so if s="aabaaaacdmmmmmm", k=2

We split on "b" first then evaluate aa then split on "c" and get aabaaaa not sure what we are getting the max of

def longestSubstring(s, k):
    for c in set(s):
        if s.count(c) < k:
            return max(longestSubstring(t, k) for t in s.split(c))
    return len(s)
Solution

  • If c == 'b', s.split(c) splits the input into

    ['aa', 'aaaacdmmmmmm']

    It then calls itself recursively to get the length of the longest substring in each of these.

    longestSubstring('aa', 2) will return 2 because none of the characters have frequency less than 2.

    longestSubstring('aaaacdmmmmmm', 2) will do some more recursion, eventually returning 6 because that's the length of mmmmmm.

    max(2, 6) returns 6, which is returned by the function.