Python 56ms solution


  • 2
    A
    class Solution(object):
        def longestSubstring(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            if len(s) < k:
                return 0
            mydict, myset = {}, set()
            for c in s:
                if c in mydict.keys():
                    mydict[c] += 1
                else:
                    mydict[c] = 1
                if mydict[c] >= k:
                    myset.discard(c)
                else:
                    myset.add(c)
            if len(myset) == 0:
                return len(s)
            intervals, start = [], 0
            while start < len(s):
                if s[start] not in myset:
                    i = start
                    while start < len(s):
                        if s[start] not in myset:
                            start += 1
                        else:
                            break 
                    intervals.append((i, start))
                else:
                    start += 1
            gMax = 0
            for interval in intervals:
                gMax = max(gMax, self.longestSubstring(s[interval[0]:interval[1]], k))
            return gMax
    

  • 0

    Am I right in thinking that it's O(N lg N) by the Master Theorem, case 2? In the worst case, you split the input into k intervals of roughly N/k size each, which makes it T(N) = k f(N/k) + O(N), therefore the complexity is O(N^(log_k(k))*log_k(N)) = O(N lg N).


  • 0
    A

    @stachenov said in Python 56ms solution:

    ase 2?

    yes, I think so.


  • 0
    C

    @AlgoGuruZ Hi AlgoGuruz, can you write some common or give a brif explanation of your solution? cos, I am very curious about your O(nlogn) solution, but I am not familiar with python, which makes me feel embrassed when I face your code.


  • 0
    A

    @dader sure, and sorry for being lazy on comments. Actually, @stachenov 's comment is exactly right on what my piece of code does.


  • 1

    No, wait a moment. N/k is not the worst case. The worst case is when one of your intervals is almost N, so you end up solving the same thing for a slightly smaller problem again and again. That's O(N^2), much like the worst case for Quicksort.


  • 0
    T

    If you remove the recursion and calculate the gMax instead of inserting to intervals you almost have an accepted solution. That modified version of yours failed only on (my own test cases):

    "aaabbbcdefcdefcde"
    3
    "aaabbbcdefcdefgggggggggggggggcde"
    3
    

    While I was developing my linear solution I went through a similar pass where these test cases failed in my suite. That's when I needed to add the Validator class.


  • 0

    It appears that this is neither O(N^2) nor O(N log N). It's O(N)! We all forgot about string containing only 26 letters at most. Hence, even in the worst case you only have to split the string 26 times, so you get O(26N). For a larger alphabet, it's worst-case O(MN), where M is the alphabet size.


  • 0
    W

    Your divide and conquer idea is good and pretty much like Stefan's~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.