GeetCode Hub

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.

Example 4:

Input: s = ""
Output: 0

 

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

class Solution { public: int lengthOfLongestSubstring(string s) { if(s.length()<=1) return s.length(); map <char,pair<int,int>> m; int length=0,mx=0,i,j=0; for(i=0;i<s.length();i++) { if(m[s[i]].second>0 && m[s[i]].first>=j) { length=i-j; mx=max(mx,length); j= m[s[i]].first+1; } m[s[i]].first=i; m[s[i]].second++; length=i-j+1; } mx=max(length,mx); return mx; } };

The basic idea of solving this problem is to keep track of all the characters we have already visited and maintain a window size in which each character appeared only once. So throughout the traversal whenever the window size is maximum, that will give us the result.

 

Time Complexity: O(n)  // For traversing all the items in the array.

Space Complexity: O(n) // for keeping track of already visited items in the window, in the worst case all items will be present in the HashSet.