Problem:

Q3. 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.

Constraints:

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

Solution:

A simple approach to the problem will checking every substring of the string have any repeating characters and return the longest one.
But the Time complexity of such code will be O(n^2).

We can use a much more optimized solution using sliding window. Let's see how we can implement it.

Approach (Sliding Window):

We can use a sliding window to solve this problem. The sliding window is a technique that uses two pointers to keep track of a substring in a string. The two pointers are the start and end of the substring. We use the end pointer to expand the substring until we get a repeating character in the substring. At this point, we contract (start pointer) and repeat the same process again until we get a substring without any repeating characters. The algorithm is as follows:

1. Create a set to store the characters in the current window.
2. Create some variables lString to store the length of the longest substring without repeating characters, start to store the start of the current window, and end to store the end of the current window.
3. Loop through the string s from start to end.
4. If the character at the end pointer is not in the set, then add it to the set and increment the end pointer.
5. If the character at the end pointer is in the set, then remove the character at the start pointer from the set and increment the start pointer.
6. Update the length of the longest substring without repeating characters.
7. Return the length of the longest substring without repeating characters.

Now, we can write the code:

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        vector<int> v(256, 0);
        int start = 0, lString = 0;
        for (int end = 0; end < s.length(); end++)
        {
            v[s[end]]++;
            while (v[s[end]] > 1)
            {

                v[s[start]]--;
                start++;
            }
            lString = max(lString, end - start + 1);
        }
        return lString;
    }
};

int main()
{
    Solution s;
    string str = "abcabcbb";
    cout << s.lengthOfLongestSubstring(str);
    return 0;
}

Complexity Analysis:

Time Complexity: O(n)
Space Complexity: O(1)
Hope this helps!

• If you have any questions, please leave a comment below. 💭
  

• If you like this article, please share it with your friends. 💖
  

• If you want to read more articles like this, please follow me.
  

Thank you for reading!