12 lines Python


  • 69

    The current window is s[i:j] and the result window is s[I:J]. In need[c] I store how many times I need character c (can be negative) and missing tells how many characters are still missing. In the loop, first add the new character to the window. Then, if nothing is missing, remove as much as possible from the window start and then update the result.

    def minWindow(self, s, t):
        need, missing = collections.Counter(t), len(t)
        i = I = J = 0
        for j, c in enumerate(s, 1):
            missing -= need[c] > 0
            need[c] -= 1
            if not missing:
                while i < j and need[s[i]] < 0:
                    need[s[i]] += 1
                    i += 1
                if not J or j - i <= J - I:
                    I, J = i, j
        return s[I:J]

  • 0

    Cool code! It's been a long time since the last time I read your code :-)


  • 1
    L

    Translating your idea into C#, which is ugly longer, while I'm using a Queue to track the left "valid" indices in O(1) time but not step one by one as seems a bit improved :-)

    public string MinWindow(string s, string t) {
        if(s.Length < t.Length || t.Length == 0) return "";
        int left = -1, right = s.Length - 1, iLeft = 0, iRight = 0, count = 0;
        Dictionary<char, int> dict = new Dictionary<char, int>();
        for(int i = 0; i < t.Length; i++)
            if(!dict.ContainsKey(t[i])) dict[t[i]] = 1;
            else dict[t[i]]++;
        Queue<int> queue = new Queue<int>();
        while(iRight < s.Length){
            if(dict.ContainsKey(s[iRight])){
                queue.Enqueue(iRight);
                if(--dict[s[iRight]] >= 0) count++;
                if(count == t.Length){
                    iLeft = queue.Dequeue();
                    if(iLeft == iRight) return t;
                    while(count == t.Length)
                        if(++dict[s[iLeft]] > 0) count--;
                        else iLeft = queue.Dequeue();
                    if(iRight - iLeft < right - left)
                    { right = iRight; left = iLeft; }
                }
            }
            iRight++;
        }
        return left == -1 ? "" : s.Substring(left, right - left + 1);
    }

  • 6
    J
        def minWindow(self, s, t):
            m = len(s)
            n = len(t)
            if m < n:
                return ''
            lt = {}
            for i in t:
                if i not in lt:
                    lt[i] = 1
                else:
                    lt[i] += 1
            missing = n
            i = I = J = 0
            for j, c in enumerate(s, 1):    
                if c in lt and lt[c] > 0:
                    missing -= 1
                if c in lt:
                    lt[c] -= 1
    
                while i < j and not missing:
                    if not J or j-i < J-I:
                        I, J = i, j
                    if s[i] not in lt:
                        i += 1
                        continue
                    else:
                        lt[s[i]] += 1
                        if lt[s[i]] > 0:
                            missing += 1
                        i += 1
            return s[I:J]
    

    Smart solution! I followed your idea and modified it into a version without using Counter. Happy to hear your comments on using or not using Counter. Thank you.


  • 3
    Z

    sometimes it is hard to believe you write so short for a HARD problem and still easy to read.


  • 0
    Y

    I ever know this algorithm but i cannot believe you write it so concisely


  • 0
    This post is deleted!

  • 0
    N

    @StefanPochmann Would it be really O(n) considering dictionary lookup (with could be O(n) in worst case itself)?


  • 0

    @niksite Just following the apparent convention to treat hash table operations as O(1). See here for a little discussion we had about it recently.


  • 0
    R
    This post is deleted!

  • 0
    R

    @rapters1983 said in 12 lines Python:

    def minWindow(self, s, t):
        need, missing = collections.Counter(t), len(t)
        i = I = J = 0
        for j, c in enumerate(s, 1):
            missing -= need[c] > 0
            need[c] -= 1
            if not missing:
                while i < j and need[s[i]] < 0:
                    need[s[i]] += 1
                    i += 1
                if not J or j - i <= J - I:
                    I, J = i, j
                missing = 1 #skip the first char in min-window
                need[s[i]] += 1
                i += 1
        return s[I:J]

  • -3
    T

    Wow, this code is amazing. Thanks for sharing it!

    One thing I don't understand is, I had to add this line after handling the not missing case otherwise it exceeds the time limit. How does your code handle the slow pointer after the not missing case?

          missing = 1
          need[s[i]] += 1 if need[s[i]]
          i += 1
    

    I've included my Ruby code based on yours:

    # param {String} s
    # param {String} t
    # return {String}
    def min_window(s, t)
      need = {}
      t.each_char do |c|
        need[c] ||= 0
        need[c] += 1
      end
      i = j = a = b = 0
      missing = need.length
      s.each_char do |c|
        j += 1
        need[c] -= 1 if need[c]
        missing -= 1 if need[c] && need[c] == 0
        if missing <= 0
          while i < j && (need[s[i]].nil? || need[s[i]] < 0)
            need[s[i]] += 1 if need[s[i]]
            i += 1
          end
          a, b = i, j if b == 0 || (b-a > j-i)
          missing = 1
          need[s[i]] += 1 if need[s[i]]
          i += 1
        end
      end
      return s[a...b]
    end
    

  • -1
    L
    This post is deleted!

  • 0

    @livelearn I don't remember why I did that. Maybe to correctly handle cases like s = "a", t = "", where your version crashes.


  • -1
    L
    This post is deleted!

  • 0
    Z

    Great solution I love it! and it seems like the i < j check on line 8 is not necessary, since we are checking need[s[i]] < 0, so we must have seen s[i] before so there is no way i could go over j.


  • 0

    @zhongyuan9817 I think that's what @livelearn said as well, see my reply above.


  • 0
    Z

    @StefanPochmann Yeah, @livelearn 's comments was deleted, so couldn't see what he has asked, now it make a lot sense. thank you


  • 0
    D

    really incredible, orz ! !


  • 0

    I wrote C# code based on implementation by @lestrois.

    What can I say after I debug the code using a test case? The idea is not intuitive; in other words, there should be a strong motivation to do that, time complexity is better. One dictionary serves multiple purposes. It reminds me the algebra.

    For example, "xxyz", search string is "xyz".
    We can keep the search string in the dictionary<char, int>
    dict['x'] = 1,
    dict['y'] = 1,
    dict['z'] = 1

    Now, we like to use those values to track how many in the sliding window. If the sliding window is "xx", then dict['x'] = -1. If the value is 0, then the number of char is exactly what need. -1 means that there is extra one.

    We also keep count of how many chars we need in search string. First visit of x in sliding window "xx" we increment count variable once, but second one we do not do that. In other words, there is only one 'x' in search string. From any iteration, it is easy to tell if the sliding window contains the search string by comparing count variable with the length of search string.

    Queue is not necessary, just track the left position of sliding window. One advantage to use queue is to filter out characters not in the search string.

    Most important is to check time complexity of this idea, it is better than O(s.Length * t.Length), actually it is O(s.Length).

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace minimumWindowSubstring_Shortversion
    {
        class minimumWindowSubstring_Shortversion
        {
            static void Main(string[] args)
            {
                RunTestcase(); 
            }
    
            public static void RunTestcase()
            {
                var result = MinWindow("xxyz", "xyz");
            }
    
            public static string MinWindow(string s, string t)
            {
                if (s.Length < t.Length || t.Length == 0)
                {
                    return "";
                }
    
                int length  = s.Length;
                int tLength = t.Length; 
    
                int minimumSubstring_left  = -1;
                int minimumSubstring_right = length - 1;                                 
    
                var dict = new Dictionary<char, int>();
    
                for (int i = 0; i < tLength; i++)
                {
                    var visit = t[i];
                    if (!dict.ContainsKey(visit))
                    {
                        dict[visit] = 1;
                    }
                    else
                    {
                        dict[visit]++;
                    }
                }
    
                int left = 0; 
                int index = 0;
                int count = 0;
                var queue = new Queue<int>();
                while (index < length)
                {
                    var visit = s[index];
    
                    if(!dict.ContainsKey(visit))
                    {
                        index++;
                        continue; 
                    }
                    
                    queue.Enqueue(index);
                    --dict[visit];
    
                    if (dict[visit] >= 0)
                    {
                        count++; // count is the number of chars visited required in search string
                    }
    
                    if (count == tLength) 
                    {
                        left = queue.Dequeue();
                        if (left == index) // ?
                        {
                            return t;
                        }
    
                        while (count == tLength)
                        {
                            var leftChar = s[left];
    
                            ++dict[leftChar]; // ?
                            if (dict[leftChar] > 0) 
                            {
                                count--;
                            }
                            else
                            {
                                left = queue.Dequeue();
                            }
                        }
    
                        if (index - left < minimumSubstring_right - minimumSubstring_left)
                        { 
                            minimumSubstring_right = index; 
                            minimumSubstring_left  = left; 
                        }
                    }                
    
                    index++;
                }
    
                return minimumSubstring_left == -1 ? "" : s.Substring(minimumSubstring_left, minimumSubstring_right - minimumSubstring_left + 1);
            }
        }
    }

Log in to reply
 

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