LeetCode 76 Minimum Window Substring (C++)

-
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution C++


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    string minWindow(string S, string T) {
        int needToFind[256] = {0};
        int alreadyFound[256] = {0};
        int count = 0;
        int slen = S.length();
        int tlen = T.length();
        for (int i = 0; i < tlen; ++i) {
            needToFind[T[i]] ++;
        }

        int mstart = 0;
        int maxlen = numeric_limits<int>::max();
        bool found = false;
        int begin = 0;
        int end = 0;
        for (; end < slen; ++end) {
            if (needToFind[S[end]] == 0) continue;
            if (alreadyFound[S[end]] < needToFind[S[end]]) {
                count ++;
            }
            alreadyFound[S[end]] ++;
            if (count == tlen) {
                while (alreadyFound[S[begin]] == 0 || alreadyFound[S[begin]] > needToFind[S[begin]]) {
                    if (alreadyFound[S[begin]] > needToFind[S[begin]])
                        alreadyFound[S[begin]] --;
                    ++ begin;
                }
                if (end - begin + 1 < maxlen) {
                    found = true;
                    maxlen = end - begin + 1;
                    mstart = begin;
                }
            }
        }
        if (!found) return "";
        return S.substr(mstart, maxlen);
    }
};

Popular posts from this blog

How Django Works (4) URL Resolution

-
Image
Why We Need URL Resolution Theoretically, we could write a single function to process all incoming HTTP requests. It would work well for very simple websites. For any real websites, it would be much more appropriate to categorize HTTP requests based on their URLs and process them separately in different handlers. For example, BASEURL/polls/ would be an application for polls whereas BASEURL/blogs/ would be an application for blogs. This way, different URLs can be considered different logic applications, so we can think of websites in terms of logic applications – a higher level of abstraction that HTTP request/response pairs. Fortunately, many modern web frameworks come default with mechanisms that do the categorization of HTTP requests based on URIs, which spares us the effort of having to reinvent the wheel.   Django's URL Resolution The official Django document has following description about how Django processes a request. https://docs.djangoproject.com/en/1.8/topic...
Read more

Python Class Method and Class Only Method

-
In this post, I will be discussing Python method especially class method. Example class Foo : def bar_inst ( self ): print ( self , "This is bar_inst" ) @staticmethod def bar_static (): print ( "This is bar_static" ) @classmethod def bar_class (cls): print (cls, "This is bar_class" ) >>> foo = Foo() >>> foo.bar_inst <bound method Foo.bar_inst of <test.Foo object at 0x025A0EB0>> >>> foo.bar_static <function Foo.bar_static at 0x025A34F8> >>> foo.bar_class <bound method type.bar_class of <class 'test.Foo'>> foo.bar_static just returns a function object as if bar_static were defined outside of class. (In Python 2, it would return an unbound method; Python 3 has removed the concept of unbound methods. So a function is either a bound method or a regular function object) How It Works -- Descriptor  Every ...
Read more

How Django Works (1)

-
How websites work in general The way every website works can be simplified as a pair of HTTP request and response. A user sends an HTTP request through a client, most likely one of those browsers, such as Firefox, Chrome; Upon receiving the HTTP request, the website processes the request and sends back an HTTP response. At HTTP level, every website works this way. They have no knowledge about module, view, template, controller, or any other fancy terms. Below is the HTTP request and response pair generated by me accessing my localhost, where I am running polls – the Django tutorial website. Request GET /polls/ HTTP/1.1 Host: 127.0.0.1:8000 Connection: keep-alive Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8 Upgrade-Insecure-Requests: 1 User-Agent: Mozilla/5.0 (X11; Linux i686) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/44.0.2403.125 Safari/537.36 Accept-Encoding: gzip, deflate, sdch Accept-Language: en-GB,en;q=0.8,en-US...
Read more