Length of the Longest Substring Without Repeating Characters

DevSniper
Published : 22 July 2024

204 Views

String Coding Problems Two Pointes DSA

Given a string str, your task is to find the length of the longest substring without repeating characters.

Example 1 :-

str : abcdeabfdcbdb

Output : 6

Example 2 :-

str : rrrrrrrrrrrr

Output : 1

Constraints :

0 <= str.length <= 5 * 10^4
str consists of English letters, digits, symbols and spaces.

Brute force Approach

Brute force Approach is to take all substrings one by one and check whether it contains all unique characters or not. For checking a substring contains all unique characters or not. This can be checked efficiently by scanning each substring from left to right and using a map to track visited characters.

C++

Java

Python

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

bool isAllUniqueChar(string str, int i, int j)
{
    vector<bool> visited(256);
    for (int k = i; k <= j; k++) {
        if (visited[str[k]] == true)
            return false;
        visited[str[k]] = true;
    }
    return true;
}
int longestUniqueSubstring(string str)
{
    int n = str.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isAllUniqueChar(str, i, j)) {
                ans = max(ans, j - i + 1);
            }
        }
    }
    return ans;
}
int main()
{
    string str="rebootmemory";
    cout<<longestUniqueSubstring(str)<<endl;
}

Time Complexity : O(N^3)

Space Complexity : O(N)

Using Two Pointer OR O(N^2) Sliding Window

Idea behind this approach is using two pointers left and right along with a max_length variable. The left pointer marks the beginning of the substring and the right pointer expands the substring until it reach a duplicate character or reaches the end of the string. max_length is updated and the left pointer is moved forward to find a new substring without duplicates. This process continues until the entire string is traversed.

C++

Java

Python

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

int longestUniqueSubstring(string str)
{
    int n = str.size();
    int max_length = 0;
    for (int i = 0; i < n; i++) {
        unordered_set < int > set;
        int j;
        for ( j = i; j < n; j++) {
            if (set.find(str[j]) != set.end()) {
                max_length = max(max_length, j - i );
                break;
            }
            set.insert(str[j]);
        }
        max_length = max(max_length, j - i );
    }
    return max_length;
}
int main()
{
    string str="rebootmemory";
    cout<<longestUniqueSubstring(str)<<endl;
}

Time Complexity : O(N^2)

Space Complexity : O(N)

Using Sliding Window O(N) Time Complexity

Using sliding window we can solve this problem in liner time complexity.

Steps :

Create and initialize variables :- one max_len , two pointers left and right and initialize with 0 and a set to maintain character of sliding window.
Iterate over array
1. Verify if character is present in the sliding window or not.
2. If present that means repeating character occur. update max_len variable with current window. Remove the leftmost character from the current window and shift the left pointer to the right do this until the repeating character is removed from the current window.
3. Insert right pointer character in set(current window) and move right pointer ahead.
update max_len with current window

C++

Java

Python

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

int longestUniqueSubstring(string str)
{
    int n = str.size();
    int max_length = 0;
    int left =0,right=0;
    unordered_set <char> set;
    for ( ; right < n; right++) {
        if(set.find(str[right]) != set.end()) {
            max_length = max(max_length, right - left );
            while(set.find(str[right]) != set.end()) {
                set.erase(str[left]);
                left++;
            }
        }
        set.insert(str[right]);
    }
    max_length = max(max_length, right - left );
    return max_length;
}
int main()
{
    string str="rebootmemory";
    cout<<longestUniqueSubstring(str)<<endl;
}

Time Complexity : O(N)

Space Complexity : O(N)

Using Sliding Window II

In the above approach when a repeating character is encountered in the sliding window. We use a loop to adjust the left pointer until the repeating character is removed from the sliding window. This can be optimized by storing the index of each character to facilitate direct adjustment of the left pointer without needing to iterate through the window.

C++

Java

Python

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

int longestUniqueSubstring(string str)
{
    int n = str.size();
    int max_len = 0;
    int left =0,right=0;
    unordered_map <char,int> map;
    for ( ; right < n; right++) {
        if (map[str[right]] != -1) {
            max_len = max(max_len, right - left );
            left = max(map[str[right]] + 1, left);
        }
        map[str[right]]=right;
    }
    max_len = max(max_len, right - left );
    return max_len;
}
int main()
{
    string str="rebootmemory";
    cout<<longestUniqueSubstring(str)<<endl;
}

Time Complexity : O(N)

Space Complexity : O(N)