5ms Java solution


  • 0
    M
    public class Solution {
        public String minWindow(String s, String t) {
            int[] cnt = new int[225];
            for (int i = 0; i < 225; i++) {
                cnt[i] = Integer.MIN_VALUE;
            }
            int c;
            int tLen = t.length();
            int sLen = s.length();
            char[] cS = s.toCharArray();
            char[] cT = t.toCharArray();
            
            for (int i = 0; i < tLen; i++) {
                c = cT[i] - (char)0;
                if (cnt[c] == Integer.MIN_VALUE) {
                    cnt[c] = 0;
                }
                cnt[c]++;
            }
            
            int i = 0;
            int j = 0;
            int okNum = 0;
            int bestLen = sLen + 1;
            int bestI = 0;
            int bestJ = 0;
            int tmp;
            boolean found = false;
            while (j < sLen || (j == sLen && okNum == tLen)) {
                if (okNum < tLen) {
                    c = cS[j++] - (char)0;
                    if (cnt[c] > Integer.MIN_VALUE) {
                        tmp = cnt[c];
                        if (tmp > 0) {
                            okNum++;
                        }
                        cnt[c] = tmp - 1;
                    }
                }
                else {
                    c = cS[i++] - (char)0;
                    if (cnt[c] > Integer.MIN_VALUE) {
                        tmp = cnt[c];
                        if (tmp >= 0) {
                            okNum--;
                        }
                        cnt[c] = tmp + 1;
                    }
                }
                if (okNum == tLen && bestLen > j - i) {
                    bestLen = j - i;
                    bestI = i;
                    bestJ = j;
                    found = true;
                }
            }
            if (!found) {
                return "";
            }
            return s.substring(bestI, bestJ);
        }
    }
    

    Thanks to @alpenliebe's hint (Didn't look at his solution, though :-P)!
    Using array instead of Map makes 32ms solution 5ms. But this assumes the input only contains ASCII characters.


  • 0
    A

    Do not use a map. A array will do the trick. Check my solution


  • 1
    A

    Do not use a map. A array will do the trick. Check my solution

    Fast 7ms solution


Log in to reply
 

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