O(n) 5ms Java Solution Beats 93.18%


  • 8
    L

    This solution adopts the idea described in this LeetCode article. It explains this O(n) solution very well. Because of that article, I kept the comments simple. I highly suggest you to read it before trying this code.

    public class Solution {
      public String minWindow(String s, String t) {
        char[] needToFind = new char[256];
        char[] hasFound = new char[256];
        int sLen = s.length();
        int tLen = t.length();
        int count = 0;
        int optLen = Integer.MAX_VALUE; // opt stands for optimal
        int optBegin = 0;
        int optEnd = 0;
        for (int i = 0; i < tLen; i++) { // gives a counter for each character in t
          needToFind[t.charAt(i)]++;
        }
        for (int begin = 0, end = 0; end < sLen; end++) {
          if (needToFind[s.charAt(end)] == 0) { // skips irrelevant char
            continue;
          }
          char currEnd = s.charAt(end); // the char at the end
          hasFound[currEnd]++;
          if (hasFound[currEnd] <= needToFind[currEnd]) {
            count++;
          }
          if (count == tLen) { // pauses end, moves beginning to the right as much as possible
            char currBegin = s.charAt(begin); // char at begin
            while (hasFound[currBegin] > needToFind[currBegin] || needToFind[currBegin] == 0) {
              if (hasFound[currBegin] > needToFind[currBegin]) {
                hasFound[currBegin]--;
              }
              begin++;
              currBegin = s.charAt(begin);
            }
            if (optLen > end - begin + 1) { // if current length is smaller, update our optimum solution
              optLen = end - begin + 1;
              optBegin = begin;
              optEnd = end;
            }
          }
        }
        if (count != tLen) {
          return "";
        }
        return s.substring(optBegin, optEnd + 1);
      }
    }
    

  • 0
    K

    @Longstation hi

    Can you tell me how can I pint the content of needToFind & hasFound char array. I want to see what it looks like actually,
    because when I trued to print this array...

    at line 18 I am trying to print but getting nothing there for my string ["S = ADOBECODEBANC"; t= "ABC"]

      char currEnd = s.charAt(end); // the char at the end
      System.out.println(" Frequency of Char "  + currEnd + " is " + hasFound[currEnd]) ;  
    

    Frequency of Char A is 
    Frequency of Char B is 
    Frequency of Char C is 


Log in to reply
 

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