3. Longest Substring Without Repeating Characters

Problem Statement

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.

Constraints:

• 0 <= s.length <= 5 * 104

• s consists of English letters, digits, symbols and spaces.

Intuition

Approach:

Sliding Window using HAsh MAp

Links

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Video Links

Approach 1:

Slinding Window + MAp

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        int low = 0, high = 0;
        int ans = 0;

        while(high<s.size()){
            if(mp.find(s[high]) == mp.end()){
                mp[s[high]]++;
            }
            else{
                while(s[low] != s[high]){
                    mp.erase(s[low]);
                    low++;
                }
                low++;
            }
            ans = max(ans, high-low+1);

            high++;
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems