Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

Examples

Example 1:

Input: s = “abcabcaa”

Output: 3

Explanation: The longest substring without repeating characters is "abc", which has a length of 3.

Example 2:

Input: s = “aaaaa”

Output: 1

Explanation: The longest substring without repeating character is “b”, which has a length of 1.

Different Approaches

1 Brute Force Approach

A brute force approach to solve this problem would be to generate all possible substrings of the given string and check each substring for repeating characters. We keep track of the length of the longest substring without repeating characters and return it as the result.

Algorithm:

Code Implementation C++:

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int lengthOfLongestSubstring(string s) {
    int n = s.size();
    int max_length = INT_MIN;

    // Iterate through each character in the string
    for (int i = 0; i < n; i++) {
        unordered_set<char> seen; // Set to store characters seen in the current substring
        int length = 0; // Length of the current substring

        // Iterate through the string starting from the current character
        for (int j = i; j < n; j++) {
            // If the current character is already seen in the current substring, break the loop
            if (seen.find(s[j]) != seen.end()) {
                break;
            }
            // Add the current character to the set of seen characters
            seen.insert(s[j]);
            length++; // Increment the length of the current substring
        }

        // Update the maximum length of the substring without repeating characters
        max_length = max(max_length, length);
    }

    return max_length;
}

int main() {
    string s = "abcabcbb";
    cout << "Length of the longest substring without repeating characters: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity: O(N^2)

Space Complexity: O(N), where N is the size of HashSet used for storing the elements.

2 Optimized Approach (Using Set and Sliding Window)

Code Implementation in C++:

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

// Function to find the length of the longest substring without repeating characters
int lengthOfLongestSubstring(string s) {
    int n = s.size();
    int left = 0, right = 0;
    int max_length = 0;
    unordered_set<char> window; // Set to keep track of characters in the current window

    // Iterate through the string using the sliding window approach
    while (right < n) {
        // If the character s[right] is not in the window, add it to the window and expand the window to the right
        if (window.find(s[right]) == window.end()) {
            window.insert(s[right]);
            right++;
            // Update max_length with the maximum length of the current substring
            max_length = max(max_length, right - left);
        } else { // If the character s[right] is already in the window, remove s[left] from the window and shrink the window from the left
            window.erase(s[left]);
            left++;
        }
    }

    return max_length; // Return the length of the longest substring without repeating characters
}

int main() {
    string s = "abcabcbb";
    cout << "Length of the longest substring without repeating characters: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity:O(n)

• The algorithm traverses the string once using the two-pointer sliding window approach.
• Both left and right pointers traverse the string once from left to right.
• Hence, the time complexity of the algorithm is O(n), where n is the length of the input string.

Space Complexity: O(n)

• We use an unordered set window to keep track of characters in the current window.
• The size of the window can grow at most up to the size of the input string.
• Hence, the space complexity of the algorithm is also O(n), where n is the length of the input string.

3 Sliding Window (using map)

Code Implementation in C++:

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int lengthOfLongestSubstring(string s) {
    int n = s.size();
    int left = 0, right = 0;
    int max_length = 0;
    unordered_map<char, int> window;

    while (right < n) {
        if (window.find(s[right]) != window.end()) {
            while (left < right && window.find(s[right]) != window.end()) {
                window.erase(s[left]);
                left++;
            }
        }
        window[s[right]]++;
        right++; // Move the right pointer forward
        max_length = max(max_length, right - left); // Update max_length with the length of the current substring
    }

    return max_length;
}

int main() {
    string s = "abcabcbb";
    cout << "Length of the longest substring without repeating characters: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity: O(n)

Space Complexity:O(n)