11.Longest Substring Without Repeating Characters

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.

Solution I: (Bruteforce Approach)

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {

        int maxLen = 0,i,j;
        for (i = 0; i < s.length(); i++)
        {
            unordered_set<char> k;
            for (j = i; j < s.length(); j++)
            {
                if (k.find(s[j]) == k.end())
                {
                    k.insert(s[j]);
                }
                else
                {
                    break;
                }
            }
            
            int len = j - i;
            if (len > maxLen)
            {
                maxLen = len;
            }
        }

        return maxLen;
    }
};

Time Complexity: O(n^2), Space Complexity: O(n)

Optimized Solution: (Sliding Window Technique)

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {

        unordered_map<char, int> m;
        int start = 0;
        int res = 0;

        for (int i = 0; i < s.length(); i++)
        {

            if (!m[s[i]])
            {
                m[s[i]]++;
            }
            else
            {
                while (m[s[i]])
                {
                    m[s[start]]--;
                    start++; 
                }

                m[s[i]]++;
            }

            res = max(res, (i - start)+1 );
        }

        return res;
    }
};

Time Complexity: O(n), Space Complexity: O(n)