Sliding Window: Given a string you need to find the longest non repeating substring

Problem Statement:

You are given a string, you need to find the length of the longest substring without duplicate characters

Example:

Input: s = "abcaaabbbcc"

Output: 3

Explanation: "abc"

Solution Explanation:

We will use sliding window to solve the problem.

Take 2 pointers i and j, for left and right respectively, the window [i..j] will always have the unique character.

Take set to keep track of the current window and if a duplicate is found, shrink the window from left.

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

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

int solution(string s) 
{
    unordered_set<char> set;  
    int i = 0, j = 0, n = s.size(), ans = 0;

    while(i < n && j < n)
    {
        if(set.find(s[j]) == set.end()) 
        {
            set.insert(s[j++]);
            ans = max(ans, j - i);
        }
        else
        {
            set.erase(s[i++]);
        }
    }
    return ans;
}

int main()
{
    string str = "abcaaabbbcc";

    cout << solution(str) << endl;

    return 0;
}

Output

3