Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- TC O(N)
- Logic:we will have a window and a map,map will store count of all chars in window.
- we will keep count of distinct character of window using map and when it equals to
- distinct characters in map,then we have a substring with all distinct character
- .now there is possibility that some characters got repeated
- so we will shrink our window from left dise till our window have every distinct character
- then we will update our ans.now we will reduce one distinct character from our window
- and search for other possibility and do same for new window.
- */
- class Solution{
- public:
- int findSubString(string s){
- set<char> st;
- for(auto itr:s){ //find distinct characters in string
- st.insert(itr);
- }
- int target=st.size(); //total distinct characters in string
- int distinct=0;
- unordered_map<char,int> mp; //it will store the frequency of characters of window
- int l=0,r=0,ans=INT_MAX,cur=0;
- for(int i=0;i<s.size();i++){
- if(mp[s[i]]!=0){
- mp[s[i]]++;
- }
- else{
- cur++; //if frequency is 0,means new char in window
- mp[s[i]]++; //so it will contribute in distinct characters
- if(cur==target){
- while(l<s.size() && mp[s[l]]>1){mp[s[l]]--;l++;} //shrink the window from left
- ans=min(ans,(i-l+1));
- mp[s[l]]--;
- cur--;
- l++;
- }
- }
- }
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement