Python solution with detailed explanation

  • 0


    Longest Substring with At Most Two Distinct Characters

    General Idea
    This question belong to the same category as those such as "longest substring without repeating characters", "minimum window substring", and "substring with concatenation of all words". To solve this kind of question we can use two pointers and a hash table. When the key of the hash table is char, we can simply use an array as the hash table. The most important idea in solving this kind of questions is "how to update the "start" pointer" and the solution to these questions seem usually differ only in this respect.


    • Maintain two pointers: start and end
    • Move end till you keep getting a good solution.
    • Once you break the constraint, move start to right till you get the constrain right again.
    from collections import defaultdict
    class Solution(object):
        def lengthOfLongestSubstringTwoDistinct(self, s):
            :type s: str
            :rtype: int
            st, soln, window = 0, defaultdict(set), 0
            for end in range(len(s)):
                if len(soln) <= 2:
                    window = max(window, end-st+1)
                    while st<= end and len(soln) > 2:
                        if len(soln[s[st]]) == 0:
                        st += 1
            return window

Log in to reply

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