problems/Smallest_Window_Containing_The_Substring.cpp at master · pooja002/problems · GitHub

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<bits/stdc++.h>

using namespace std;
class Smallest_Window_Containing_The_Substring
{
    public:

    static string Find_Smallest_Window_Containing_The_Substring(const string &str, const string &pattern)
    {
        int windowstart=0,matched=0,minlength=str.length()+1,substringstart=0;
        unordered_map<char,int> charfrequencymap;
        for( auto ch:pattern)
        {
            charfrequencymap[ch]++;
        }


        for(int windowend=0;windowstart<str.length();windowend++)
        {
             char right=str[windowend];
             if(charfrequencymap.find(right)!=charfrequencymap.end())
             {

              charfrequencymap[right]--;
              if(charfrequencymap[right]>=0)
              {
                  matched++;
              }
             }

             while(matched==pattern.length())
             {
                 if(minlength>windowend-windowstart+1)
                 {
                        minlength=windowend-windowstart+1;
                        substringstart=windowstart;
                 }

                 char left=str[windowstart++];

                if(charfrequencymap.find(left)!=charfrequencymap.end())
                {
                  if(charfrequencymap[left]==0)
                  {
                      matched--;
                  }
                  charfrequencymap[left]++;

                }

             }

        }
        return minlength>str.length() ? "": str.substr(substringstart,minlength);
    }

};


int main(int argc, char *argv[])
{
    cout<<Smallest_Window_Containing_The_Substring::Find_Smallest_Window_Containing_The_Substring("aabcde","b") <<endl;
}