-
Notifications
You must be signed in to change notification settings - Fork 0
/
minStringLengthContainingAllChars.cpp
93 lines (78 loc) · 2.12 KB
/
minStringLengthContainingAllChars.cpp
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// C++ program to find smallest window containing
// all characters of a pattern.
#include<bits/stdc++.h>
using namespace std;
const int no_of_chars = 256;
// Function to find smallest window containing
// all characters of 'pat'
string findSubString(string str, string pat)
{
int len1 = str.length();
int len2 = pat.length();
// check if string's length is less than pattern's
// length. If yes then no such window can exist
if (len1 < len2)
{
cout << "No such window exists";
return "";
}
int hash_pat[no_of_chars] = {0};
int hash_str[no_of_chars] = {0};
// store occurrence ofs characters of pattern
for (int i = 0; i < len2; i++)
hash_pat[pat[i]]++;
int start = 0, start_index = -1, min_len = INT_MAX;
// start traversing the string
int count = 0; // count of characters
for (int j = 0; j < len1 ; j++)
{
// count occurrence of characters of string
hash_str[str[j]]++;
// If string's char matches with pattern's char
// then increment count
if (hash_pat[str[j]] != 0 &&
hash_str[str[j]] <= hash_pat[str[j]] )
count++;
// if all the characters are matched
if (count == len2)
{
// Try to minimize the window i.e., check if
// any character is occurring more no. of times
// than its occurrence in pattern, if yes
// then remove it from starting and also remove
// the useless characters.
while ( hash_str[str[start]] > hash_pat[str[start]]
|| hash_pat[str[start]] == 0)
{
if (hash_str[str[start]] > hash_pat[str[start]])
hash_str[str[start]]--;
start++;
}
// update window size
int len_window = j - start + 1;
if (min_len > len_window)
{
min_len = len_window;
start_index = start;
}
}
}
// If no window found
if (start_index == -1)
{
cout << "No such window exists";
return "";
}
// Return substring starting from start_index
// and length min_len
return str.substr(start_index, min_len);
}
// Driver code
int main()
{
string str = "this is a test string";
string pat = "tist";
cout << "Smallest window is : \n"
<< findSubString(str, pat);
return 0;
}