C++ O(n) solution with explanation and comments


  • 0
    E

    The basic idea is to scan from right to left and record the position of each character in T. Since there can be multiple occurrences for each letter, we need a queue to store indices of all latest Ki occurrences of letter Li (Ki is the occurrence of Li in T).

    When you reach a new position, make sure you pop the rightmost position of this character from the according queue, and push the new position to the queue. That way, you always maintain the latest Ki occurrences. Why is that? Because if it is the new element who introduces a new minimum window, all the characters must be those that're closest to it.

    The code runs in O(n) complexity because each element is scanned only once, from right to left. In each step, it'll compare at most |T| times, to find the new right end of the window.

    struct tSlot
    {
       // Zero means there is no such character in T
       tSlot() : m_size(0)
       {}
    
       // For each character, store array indices of this character
       // of the latest "m_size" occurrences, in descending order.
       // We scan from right to left
       queue<int> m_indices;
    
       // The expected occurrence of this character in string T
       int m_size;
    };
    
    // Assume characters are [a, z], [A, Z]
    string minWindow(string s, string t)
    {
       if ((s.length() < t.length()) || t.empty())
          return string();
    
       vector<tSlot> map(static_cast<int>('z' - 'A' + 1));
    
       // Set the expected occurrence for each character in T
       for (int i = 0; i < t.length(); ++i)
          ++map[t[i] - 'A'].m_size;
    
       // Left, right of the min substring in S containing T
       int min_left = -1, min_right = s.length();
    
       // Used to verify if we already find a window containing T
       int count = 0;
       for (int j = s.length() - 1; j >= 0; --j)
       {
          tSlot &slot = map[s[j] - 'A'];
          // The character is not in T
          if (slot.m_size == 0)
             continue;
    
          if (slot.m_indices.size() < slot.m_size)
             ++count;
          else
             slot.m_indices.pop();
          slot.m_indices.push(j);
    
          if (count < t.length())
             continue;
    
          // Find the next min_right
          int right = -1;
          for (int k = 0; k < map.size(); ++k)
          {
             if (map[k].m_size > 0)
                right = max(right, map[k].m_indices.front());
          }
    
          if (right - j < min_right - min_left)
          {
             min_left = j;
             min_right = right;
          }
       }
    
       return (min_left == -1) ? string() : s.substr(min_left, min_right - min_left + 1);
    }

Log in to reply
 

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