Three O(N) concise implemetation according to leetcode oj discuss
// according to http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html\n    // finds the first window that satisfies the constraint\n    // then con
    // according to http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html\n    // finds the first window that satisfies the constraint\n    // then continue maintaining the constraint throughout\n    // time complexity O(2N)\n    string minWindow(string S, string T) {\n        int m = S.size(), n = T.size();\n        if (n <= 0 || m < n)\n            return "";\n        \n        int require[128] = {0}, found[128] = {0};\n        for (int k = 0; k < n; ++k) require[T[k]]++;\n        \n        int count = 0;\n        int minLen = INT_MAX, minIndex = 0;\n        for (int s = 0, e = 0; e < m; ++e) {\n            // skip characters not in T\n            if (require[S[e]] == 0) continue;\n            if (++found[S[e]] <= require[S[e]]) count++;\n            \n            // windows constrain is sastisfied\n            if (count == n) {\n                // advance begin index as far as possible\n                // stop when advancing breaks window constraint\n                while (require[S[s]] == 0 || found[S[s]] > require[S[s]]) {\n                    if (found[S[s]] > require[S[s]]) found[S[s]]--;\n                    ++s;\n                }\n                // update minmum window\n                if (e - s + 1 < minLen) {\n                    minLen = e - s + 1;\n                    minIndex = s;\n                }\n            }\n        }\n        \n        if (minLen == INT_MAX) return "";\n        return S.substr(minIndex, minLen); \n    }\n    \n    string minWindow(string S, string T) {\n        int m = S.size(), n = T.size();\n        if (n <= 0 || m < n)\n            return "";\n        \n        int require[128] = {0}, chSet[128] = {0};\n        for (int k = 0; k < n; ++k) {\n            require[T[k]]++;\n            chSet[T[k]] = 1;\n        }\n        \n        int minLen = INT_MAX, minIndex = 0;\n        int i = -1, j = 0;\n        while (i < m && j < m) {\n            if (n) {\n                ++i;\n                require[S[i]]--;\n                if (chSet[S[i]] && require[S[i]] >= 0) n--;\n            }\n            else {\n                if (minLen > i - j + 1) {\n                    minLen = i - j + 1;\n                    minIndex = j;\n                }\n                require[S[j]]++;\n                if (chSet[S[j]] && require[S[j]] > 0) n++;\n                ++j;\n            }\n        }\n        \n        if (minLen == INT_MAX) return "";\n        return S.substr(minIndex, minLen);\n    }\n\n    // the most concise one\n    // maintain a window with two pointers (left side and right side)\n    string minWindow(string S, string T) {\n        int m = S.size(), n = T.size();\n        if (n <= 0 || m < n) return "";\n        \n        int require[128] = {0};\n        for (int i = 0; i < n; ++i) require[T[i]]++;\n        \n        int count = 0;\n        int minLen = INT_MAX, minIndex = 0;\n        for (int s = 0, e = 0; e < m; ++e) {\n            require[S[e]]--;\n            if (require[S[e]] >= 0) count++;\n            while (count == n) {\n                if (e - s + 1 < minLen) {\n                    minLen = e - s + 1;\n                    minIndex = s;\n                }\n                require[S[s]]++;\n                if (require[S[s]] > 0) count--;\n                s++;\n            }\n        }\n        \n        if (minLen == INT_MAX) return "";\n        return S.substr(minIndex, minLen); \n    }
[]