Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //{ Driver Code Starts
- #include<bits/stdc++.h>
- using namespace std;
- // } Driver Code Ends
- class Solution
- {
- public:
- string smallestWindow (string s, string p)
- {
- string str=s;
- string pat=p;
- int no_of_chars=256;
- int len1 = str.length();
- int len2 = pat.length();
- if (len1 < len2) {
- return "-1";
- }
- int hash_pat[no_of_chars] = { 0 };
- int hash_str[no_of_chars] = { 0 };
- for (int i = 0; i < len2; i++)
- hash_pat[pat[i]]++;
- int start = 0, start_index = -1, min_len = INT_MAX;
- int count = 0;
- for (int j = 0; j < len1; j++) {
- hash_str[str[j]]++;
- if (hash_str[str[j]] <= hash_pat[str[j]])
- count++;
- if (count == len2) {
- 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++;
- }
- int len_window = j - start + 1;
- // cout<<len_window<<endl;
- if (min_len > len_window) {
- min_len = len_window;
- start_index = start;
- }
- }
- }
- if (start_index == -1) {
- return "-1";
- }
- return str.substr(start_index, min_len);
- }
- };
- //{ Driver Code Starts.
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- string s;
- cin>>s;
- string pat;
- cin>>pat;
- Solution obj;
- cout<<obj.smallestWindow(s, pat)<<endl;
- }
- return 0;
- }
- // } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment