-
Notifications
You must be signed in to change notification settings - Fork 0
/
longestSubstringWithoutReapeatChar.cpp
54 lines (46 loc) · 2.02 KB
/
longestSubstringWithoutReapeatChar.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
link -> https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/2133524/java-c-a-reall-detailed-explanation/
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
code*****
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.length()==0)return 0; //if string of length zero comes simply return 0
unordered_map<char,int> m; //create map to store frequency,(get to know all unique characters
int i=0,j=0,ans=INT_MIN;
while(j<s.length())
{
m[s[j]]++; //increase the frequency of the element as you traverse the string
if(m.size()==j-i+1) // whem map size is equal to the window size means suppose window size is 3 and map size is also three that means in map all unique characters are their
{
ans = max(ans,j-i+1); //compare the length of the maximum window size
}
else if(m.size()<j-i+1) //if the map size is less than the window size means there is some duplicate present like window size = 3 and map size = 2 means there is a duplicates
{
while(m.size()<j-i+1) //so till the duplicates are removed completely
{
m[s[i]]--; //remove the duplicates
if(m[s[i]]==0) //if the frequency becomes zero
{
m.erase(s[i]);//delete it completely
}
i++; //go for next element
}
}
j++; //go for the next element
}
return ans;
}
};