Problem Statement

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

Examples

Example 1:

Input: S = "abcddabac"
Output: 4

Explanation: The answer is "abcd", which has the length of 4.

Example 2:

Input: S = "aaabbccc"
Output: 2

Explanation: The answer are "ab", "bc". Both have maximum length 2.

Example 3:

Input: S = "aaaa"
Output: 1

Explanation: The only string with distinct character is "a" of length 2.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The idea here is very straightforward, first generate all the possible substrings of given array using two for loops. While finding the substrings check if the current character has occured previously with the help of a hash array. If so, no need to take this substring into consideration as characters are repeating, otherwise, calculate the length of current substring, update maximum length and finally mark the character as visited.

Approach:

1. Iterate through the array using a for loop from 0th index to sizeofArray - 1, to take all possible starting points of the substring into consideration.
2. Check if the current character is already in the hash array, if so, break out of the loop. Otherwise, as it is not visited yet, mark the character as 1 in the hash array, signifying that the current character is now visited.
3. Now, calculate the length of current substring and update the maximum length of the substrings found so far. Finally, return the maximum length

Code:

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

class Solution {
public:
    int longestNonRepeatingSubstring(string &s) {
        
        // Length of the input string
        int n = s.size(); 
        
        //Variable to store max length
        int maxLen = 0;    
        
        /* Iterate through all possible 
        starting points of the substring*/
        for (int i = 0; i < n; i++) {
            
            /* Hash to track characters in 
            the current substring window*/
            // Assuming extended ASCII characters
            vector<int> hash(256, 0);  
            
            for (int j = i; j < n; j++) {
                
                /* If s[j] is already in the
                current substring window*/
                if (hash[s[j]] == 1) break;  
                
                /* Update the hash to mark s[j]
                as present in the current window*/
                hash[s[j]] = 1;
                
                /* Calculate the length of
                the current substring*/
                int len = j - i + 1;
                
                /* Update maxLen if the current
                substring length is greater*/
                maxLen = max(maxLen, len);
            }
        }
        
        // Return the maximum length
        return maxLen; 
    }
};

int main() {
    string input = "cadbzabcd";
    
    //Create an instance of Solution class
    Solution sol;
    
    int length = sol.longestNonRepeatingSubstring(input);
    
    //Print the result
    cout << "Length of longest substring without repeating characters: " << length << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2), where N is the size of the array. Iterating the array twice using two for loops.
• Space Complexity: O(256) . Hash array to store all the characters.

2️⃣ Optimal Approach (Sliding Window Approach)

Intuition:

The idea is to use two-pointers approach to solve this problem. The two-pointer technique involves employing two indices, l (left) and r (right), which basically indicates a window starting from l and ending at r. Use a HashSet called set to keep track of characters within the current window (l to r). This allows for efficient checks and ensures no duplicates are present. While checking every window, keep track of the maximum length of subarray encountered so far.

1. Use a sliding window approach to maintain a substring without repeating characters.
2. Expand the window to the right by including new characters.
3. If a character is repeated, move the left boundary of the window forward to remove the repetition.
4. Keep track of the maximum length of valid substrings encountered.

Approach:

1. Use two pointers (left and right) to denote the current substring.
2. Use a hash map (or a set) to track the indices of characters in the current window.
3. Expand the right pointer to include a new character.
   • If the character is already in the current window, move the left pointer to skip the repeated character.
4. At each step, calculate the length of the substring (right - left + 1) and update the maximum length.
5. Repeat until the right pointer reaches the end of the string.

Dry Run:

Code:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> charIndexMap; // Map to store the last index of each character
    int maxLength = 0;
    int left = 0; // Start of the sliding window

    for (int right = 0; right < s.size(); ++right) {
        // If the character is already in the window, move the left pointer
        if (charIndexMap.find(s[right]) != charIndexMap.end() && charIndexMap[s[right]] >= left) {
            left = charIndexMap[s[right]] + 1; // Skip the repeating character
        }

        // Update the character's index
        charIndexMap[s[right]] = right;

        // Calculate the length of the current substring
        maxLength = max(maxLength, right - left + 1);
    }

    return maxLength;
}

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), where n is the number of elements.
• Space Complexity: O(k)
  • k is the size of character set (e.g., 26 for lowercase English letters, 128 for ASCII).