Longest Substring Without Repeating Characters

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:

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.

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.

Now, calculate the length of current substring and update the maximum length of the substrings found so far. Finally, return the maximum length.

#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;
}
import java.util.*;

class Solution {
    public int longestNonRepeatingSubstring(String s) {
        // Length of the input string
        int n = s.length();
        
        // 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
            int[] hash = new int[256];
            Arrays.fill(hash, 0);
            
            for (int j = i; j < n; j++) {
                
                /* If s.charAt(j) is already in the
                   current substring window */
                if (hash[s.charAt(j)] == 1) break;
                
                /* Update the hash to mark s.charAt(j)
                   as present in the current window */
                hash[s.charAt(j)] = 1;
                
                /* Calculate the length of
                   the current substring */
                int len = j - i + 1;
                
                /* Update maxLen if the current
                   substring length is greater */
                maxLen = Math.max(maxLen, len);
            }
        }
        
        // Return the maximum length
        return maxLen;
    }

    public static void main(String[] args) {
        String input = "cadbzabcd";
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        int length = sol.longestNonRepeatingSubstring(input);
        
        // Print the result
        System.out.println("Length of longest substring without repeating characters: " + length);
    }
}
class Solution:
    def longestNonRepeatingSubstring(self, s):
        # Length of the input string
        n = len(s)
        
        # Variable to store max length
        maxLen = 0
        
        """ Iterate through all possible 
            starting points of the substring """
        for i in range(n):
            
            """ Hash to track characters in 
                the current substring window """
            # Assuming extended ASCII characters
            hash_set = [0] * 256
            
            for j in range(i, n):
                
                """ If s[j] is already in the
                    current substring window """
                if hash_set[ord(s[j])] == 1:
                    break
                
                """ Update the hash_set to mark s[j]
                    as present in the current window """
                hash_set[ord(s[j])] = 1
                
                """ Calculate the length of
                    the current substring """
                current_len = j - i + 1
                
                """ Update maxLen if the current
                    substring length is greater """
                maxLen = max(maxLen, current_len)
        
        # Return the maximum length
        return maxLen

if __name__ == "__main__":
    
    input_str = "cadbzabcd"
    
    # Create an instance of Solution class
    sol = Solution()
    
    length = sol.longestNonRepeatingSubstring(input_str)
    
    # Print the result
    print("Length of longest substring without repeating characters:", length)
class Solution {
    longestNonRepeatingSubstring(s) {
        // Length of the input string
        let n = s.length;
        
        // Variable to store max length
        let maxLen = 0;
        
        /* Iterate through all possible 
           starting points of the substring */
        for (let i = 0; i < n; i++) {
            
            /* Hash to track characters in 
               the current substring window */
            // Assuming extended ASCII characters
            let hash = new Array(256).fill(0);
            
            for (let j = i; j < n; j++) {
                
                /* If s[j] is already in the
                   current substring window */
                if (hash[s.charCodeAt(j)] === 1) break;
                
                /* Update the hash to mark s[j]
                   as present in the current window */
                hash[s.charCodeAt(j)] = 1;
                
                /* Calculate the length of
                   the current substring */
                let len = j - i + 1;
                
                /* Update maxLen if the current
                   substring length is greater */
                maxLen = Math.max(maxLen, len);
            }
        }
        
        // Return the maximum length
        return maxLen;
    }
}

let input = "cadbzabcd";

//Create an instance of Solution class
let sol = new Solution();

let len = sol.longestNonRepeatingSubstring(input);

// Print the result
console.log("Length of longest substring without repeating characters: " + len);

Complexity Analysis:

Time Complexity:O(N²), 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.

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.

Approach:

Initialize few variables as: l and r pointers to 0. These pointers will define the current window [l, r] that contains characters without repetition, maxLen to 0 to store the maximum length of substring found without repeating character.

Use an array hash of size 256 (assuming ASCII characters) to store the last occurrence index of each character in the string. Initialize all elements of hash to -1, indicating that no characters have been encountered yet.

Now, while r pointer is less than sizeOfArray - 1, iterate in the array. While iterating, check if current character has occured before using hash array. If so, updadate the left pointer to index of current character plus 1. This ensures that l moves past the last occurrence of of repeated character, effectively removing the repeated character from the window.

Calculate the length of the current substring as len = r - l + 1. Update maximum length of the substring found so far.

Update hash array with the current index r, indicating the most recent occurrence of character at pointer r in the string. Finally, return maximum length of the substring.

Dry Run:

Please refer to the video for complete dry-run.

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

class Solution {
public:
    /* Function to find the longest substring
    without repeating characters*/
    int longestNonRepeatingSubstring(string& s) {
        int n = s.size();
        
        // Assuming all ASCII characters
        int HashLen = 256; 
        
        /* Hash table to store last
        occurrence of each character*/
        int hash[HashLen]; 
        
        /* Initialize hash table with
        -1 (indicating no occurrence)*/
        for (int i = 0; i < HashLen; ++i) {
            hash[i] = -1;
        }

        int l = 0, r = 0, maxLen = 0;
        while (r < n) {
            
            /* If current character s[r] 
            is already in the substring*/
            if (hash[s[r]] != -1) {
                
                /* Move left pointer to the right
                of the last occurrence of s[r]*/
                l = max(hash[s[r]] + 1, l);
            }
            
            // Calculate the current substring length
            int len = r - l + 1;
            
            // Update maximum length found so far
            maxLen = max(len, maxLen);
            
            /* Store the index of the current
            character in the hash table*/
            hash[s[r]] = r;
            
            // Move right pointer to next position
            r++;
        }
       
        // Return the maximum length found
        return maxLen;
    }
};

int main() {
    string s = "cadbzabcd"; 
    
    // Create an instance of the Solution class
    Solution sol;

    int result = sol.longestNonRepeatingSubstring(s);

    // Output the maximum length
    cout << "The maximum length is:\n";
    cout << result << endl;

    return 0;
}
import java.util.*;

class Solution {
    /* Function to find the longest substring
       without repeating characters */
    public int longestNonRepeatingSubstring(String s) {
        int n = s.length();
        
        // Assuming all ASCII characters
        int HashLen = 256; 
        
        /* Hash table to store last
           occurrence of each character */
        int[] hash = new int[HashLen];
        
        /* Initialize hash table with
           -1 (indicating no occurrence) */
        Arrays.fill(hash, -1);

        int l = 0, r = 0, maxLen = 0;
        while (r < n) {
            /* If current character s.charAt(r) 
               is already in the substring */
            if (hash[s.charAt(r)] != -1) {
                /* Move left pointer to the right
                   of the last occurrence of s.charAt(r) */
                l = Math.max(hash[s.charAt(r)] + 1, l);
            }
            
            // Calculate the current substring length
            int len = r - l + 1;
            
            // Update maximum length found so far
            maxLen = Math.max(len, maxLen);
            
            /* Store the index of the current
               character in the hash table */
            hash[s.charAt(r)] = r;
            
            // Move right pointer to next position
            r++;
        }
       
        // Return the maximum length found
        return maxLen;
    }

    public static void main(String[] args) {
        String s = "cadbzabcd"; 
        
        // Create an instance of the Solution class
        Solution sol = new Solution();

        int result = sol.longestNonRepeatingSubstring(s);

        // Output the maximum length
        System.out.println("The maximum length is:");
        System.out.println(result);
    }
}
class Solution:
    """ Function to find the longest substring
        without repeating characters """
    def longestNonRepeatingSubstring(self, s):
        n = len(s)
        
        # Assuming all ASCII characters
        HashLen = 256
        
        """ Hash table to store last
            occurrence of each character """
        hash = [-1] * HashLen
        
        """ Initialize hash table with
            -1 (indicating no occurrence) """
        for i in range(HashLen):
            hash[i] = -1

        l, r, maxLen = 0, 0, 0
        while r < n:
            """ If current character s[r] 
                is already in the substring """
            if hash[ord(s[r])] != -1:
                """ Move left pointer to the right
                    of the last occurrence of s[r] """
                l = max(hash[ord(s[r])] + 1, l)
            
            # Calculate the current substring length
            current_len = r - l + 1
            
            # Update maximum length found so far
            maxLen = max(current_len, maxLen)
            
            """ Store the index of the current
                character in the hash table """
            hash[ord(s[r])] = r
            
            # Move right pointer to next position
            r += 1
        
        # Return the maximum length found
        return maxLen

if __name__ == "__main__":
    s = "cadbzabcd"
    
    # Create an instance of the Solution class
    sol = Solution()

    result = sol.longestNonRepeatingSubstring(s)

    # Output the maximum length
    print("The maximum length is:")
    print(result)
class Solution {
    /* Function to find the longest substring
       without repeating characters */
    longestNonRepeatingSubstring(s) {
        let n = s.length;
        
        // Assuming all ASCII characters
        let HashLen = 256; 
        
        /* Hash table to store last
           occurrence of each character */
        let hash = new Array(HashLen).fill(-1);
        
        /* Initialize hash table with
           -1 (indicating no occurrence) */
        for (let i = 0; i < HashLen; ++i) {
            hash[i] = -1;
        }

        let l = 0, r = 0, maxLen = 0;
        while (r < n) {
            /* If current character s[r] 
               is already in the substring */
            if (hash[s.charCodeAt(r)] != -1) {
                /* Move left pointer to the right
                   of the last occurrence of s[r] */
                l = Math.max(hash[s.charCodeAt(r)] + 1, l);
            }
            
            // Calculate the current substring length
            let len = r - l + 1;
            
            // Update maximum length found so far
            maxLen = Math.max(len, maxLen);
            
            /* Store the index of the current
               character in the hash table */
            hash[s.charCodeAt(r)] = r;
            
            // Move right pointer to next position
            r++;
        }
       
        // Return the maximum length found
        return maxLen;
    }
}

// Main function
let s = "cadbzabcd";
let sol = new Solution();
let result = sol.longestNonRepeatingSubstring(s);

// Output the maximum length
console.log("The maximum length is:");
console.log(result);

Complexity Analysis:

Time Complexity:O(N), where N is the size of the array. As the array runs for N times.

Space Complexity: O(256) . Hash array to store all the characters.

Problem List

Longest Substring Without Repeating Characters

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code