Python solution with detailed explanation


  • 0
    G

    Solution

    Longest Substring with At Most Two Distinct Characters https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

    General Idea
    https://discuss.leetcode.com/topic/7399/share-my-c-solution/2
    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.

    Algorithm

    • 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)):
                soln[s[end]].add(end)
                if len(soln) <= 2:
                    window = max(window, end-st+1)
                else:
                    while st<= end and len(soln) > 2:
                        soln[s[st]].remove(st)
                        if len(soln[s[st]]) == 0:
                            soln.pop(s[st])
                        st += 1
            return window
    

Log in to reply
 

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