Python simple O(n) solution with comments


  • 4
    S

    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
                self.remove_lowest_char(distinct)
            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
        distinct.pop(char)

  • 0
    J
    This post is deleted!

  • 0
    C

    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
    H

    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.