Python simple O(n) solution with comments

  • 4

    Idea is simple. Maintain left to right window. If third char encountered, remove the char which has the lowest position value and update left pointer to the lowest position + 1.
    This solution can be easily extend to k distinct chars.

    class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        :type s: str
        :rtype: int
        distinct = {}  # char: pos
        maxlen = 0
        left = 0
        for right, char in enumerate(s):
            if len(distinct) == 2 and char not in distinct:
                left = min(distinct.values()) + 1
            distinct[char] = right
            maxlen = max(maxlen, right - left + 1)
        return maxlen
    def remove_lowest_char(self, distinct):
        lowest_pos = min(distinct.values())
        for k, pos in distinct.items():
            if pos == lowest_pos:
                char = k

  • 0
    This post is deleted!

  • 0

    I wonder if it costs O(n) for the remove_lowest_char function. If so, then the total time complexity should be O(n^2)

    I would like to use distinct.pop(s[left - 1]) instead.

  • 1

    How about del distinct[s[min(distinct.values())]]

Log in to reply

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