Advertisement
imashutosh51

Smallest distinct window

Jul 31st, 2022
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. /*
  2. TC O(N)
  3. Logic:we will have a window and a map,map will store count of all chars in window.
  4. we will keep count of distinct character of window using map and when it equals to
  5. distinct characters in map,then we have a substring with all distinct character
  6. .now there is possibility that some characters got repeated
  7. so we will shrink our window from left dise till our window have every distinct character
  8. then we will update our ans.now we will reduce one distinct character from our window
  9. and search for other possibility and do same for new window.
  10.  
  11. */
  12. class Solution{
  13.     public:
  14.     int findSubString(string s){
  15.        set<char> st;
  16.        for(auto itr:s){  //find distinct characters in string
  17.            st.insert(itr);
  18.        }
  19.        int target=st.size();  //total distinct characters in string
  20.        int distinct=0;
  21.        unordered_map<char,int> mp;   //it will store the frequency of characters of window
  22.        int l=0,r=0,ans=INT_MAX,cur=0;
  23.        for(int i=0;i<s.size();i++){
  24.            if(mp[s[i]]!=0){          
  25.                mp[s[i]]++;          
  26.            }
  27.            else{
  28.                cur++;                 //if frequency is 0,means new char in window
  29.                mp[s[i]]++;            //so it will contribute in distinct characters
  30.                if(cur==target){
  31.                    while(l<s.size() && mp[s[l]]>1){mp[s[l]]--;l++;}  //shrink the window from left
  32.                    ans=min(ans,(i-l+1));
  33.                    mp[s[l]]--;
  34.                    cur--;
  35.                    l++;
  36.                }
  37.            }
  38.        }
  39.        return ans;
  40.     }
  41. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement