Longest Substring Without Repeating Characters

Problem

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

Examples

Example 1:

Input: s = "aababcbb"
Output: 3
Explanation: The longest substring without repeating characters is "abc".

Example 2:

Input: s = "cccc"
Output: 1
Explanation: The longest substring without repeating characters is "c".

Example 3:

Input: s = ""
Output: 0

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/sBifMdD-IPY" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Brute Force

The trivial solution would be to do double for loop and from each position try to find the longest substring until we see a duplicate char. This is O(n^3) solution.

Another approach is we can generate substrings and check if all chars are unique, like "[Determine if a string has all unique characters](determine-if-a-string-has-all-unique-characters)" in CC 150..

Code

Java

class Solution {
     public int lengthOfLongestSubstring(String s) {
         int n = s.length();
         int ans = 0;
 
         for (int i = 0; i < n; i++) {
             for (int j = i; j < n; j++) {
                 String substring = s.substring(i, j + 1);
                 if (isUnique(substring)) {
                     ans = Math.max(ans, substring.length());
                 }
             }
         }
         return ans;
     }
     
     private boolean isUnique(String s) {
         Set<Character> seen = new HashSet<>();
         for (char c : s.toCharArray()) {
             if (seen.contains(c)) return false;
             seen.add(c);
         }
         return true;
     }
 }

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n: int = len(s)
        ans: int = 0
        
        for i in range(n):
            for j in range(i, n):
                if len(set(s[i:j + 1])) == (j - i + 1):
                    ans = max(ans, j - i + 1)
        
        return ans

Complexity

• ⏰ Time complexity: O(n^3)
  • Generating all substrings involves two nested loops, contributing O(n^2).
  • For each substring, verifying uniqueness involves another loop, adding O(n) for set-based checks. As a result, the overall time complexity is O(n^3).
• 🧺 Space complexity: O(n) for using set for checking duplicates, and it can grow to the length of the substring in the worst case.

Method 2 - Sliding Window with Set🏆

This problem is similar to the previous problem - [Longest Substring with K Distinct Characters](longest-substring-with-k-distinct-characters)

Finding the Longest substring without repeating characters is same as finding the Longest substring with All distinct characters. So instead of K distinct characters we have to find the longest substring where all characters are distinct.

We start with a window and maintain a hashset for that window. We keep on adding chars to window and slide window to right, till they are not duplicate. If we find duplicate we keep moving the left pointer to shrink window, till we remove that duplicate char from the set. In meantime, we will keep check of the longest window.

Let windowStart is left and windowEnd is right.

Code

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Initialize variables
        Set<Character> seen = new HashSet<>();
        int left = 0, ans = 0;
        
        // Iterate over the string using the "right" pointer
        for (int right = 0; right < s.length(); right++) {
            // If a duplicate character is found, shrink the window by moving "left"
            while (seen.contains(s.charAt(right))) {
                seen.remove(s.charAt(left));
                left++;
            }
            
            // Add the current character to the set and update the max length
            seen.add(s.charAt(right));
            ans = Math.max(ans, right - left + 1);
        }
        
        return ans;
    }
}

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Initialize variables
        seen: set = set()
        left: int = 0
        ans: int = 0
        
        # Iterate over the string using the "right" pointer
        for right in range(len(s)):
            # If the character is already in the set, shrink the window by moving "left"
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            
            # Add the current character to the set and update the max length
            seen.add(s[right])
            ans = max(ans, right - left + 1)
        
        return ans

Complexity

• ⏰ Time complexity: O(n). The right pointer iterates linearly over the string, processing each character exactly once. The left pointer moves forward only when duplicates are encountered. Together, this ensures linear runtime.
• 🧺 Space complexity: O(m) where m represents the number of distinct or unique characters in the string. We store these characters in a HashSet to manage the current valid window. In practical scenarios, m is bounded by the size of the character set being considered (e.g., English letters, digits, and special characters).

Method 3 - Sliding Window with Frequency Map🏆

class Solution {
	public int lengthOfLongestSubstring(String s) {
		int n = s.length();
	
		// answer - length of longest substring with no repeating chars
        int ans = 0;
		// frequency map of chars in window
		Map<Character, Integer> windowCharCnt = new HashMap<>(); 
		int left = 0;
	
		for(int right = 0; right < n; right++) {
			char c = s.charAt(right);
			windowCharCnt.put(c, windowCharCnt.getOrDefault(c, 0) + 1);
	
			while(windowCharCnt.size() < right - left + 1) {
				char leftChar = s.charAt(left);
	
                int cnt = windowCharCnt.getOrDefault(leftChar, 0) - 1;
                if (cnt <= 0) {
                    windowCharCnt.remove(leftChar);
                } else {
                    windowCharCnt.put(leftChar, cnt);
                }
	
				left++;  
			}
	
			if(windowCharCnt.size() == right-left+1) {
				ans = Math.max(ans, right-left+1);
			}
		}
	
		return ans;  
	}
}

Method 3 - Sliding Window with Boolean array as set 🏆

We can use a flag array to track the existing characters for the longest substring without repeating characters.

When we realize that substring “abcc” has dups, we can immediately abandon the whole substring and check substrings from “cdefgh”. Thus, we have the following approach:

1. Keep two pointers (start, end) that denotes the current substring we’re checking and both has an initial value of 0.
2. Each time, move forward end pointer by 1 character and use the hashset to check if the newly added character has already existed.
   1. If not, keep moving end pointer forward.
   2. If the new character is a duplicate one, move the start pointer all the way to pass the duplicate character and pop out all these characters from the hashset.
3. Repeating step 2 and output the longest substring without dup after finishing the whole string.

Code

Java

public int lengthOfLongestSubstring(String s) {
    if (s == null)
        return 0;
    boolean[] flag = new boolean[256];

    int result = 0;
    int start = 0;
    char[] arr = s.toCharArray();

    for (int i = 0; i < arr.length; i++) {
        char current = arr[i];
        if (flag[current]) {
            result = Math.max(result, i - start);
            // the loop update the new start point
            // and reset flag array
            // for example, abccab, when it comes to 2nd c,
            // it update start from 0 to 3, reset flag for a,b
            for (int k = start; k < i; k++) {
                if (arr[k] == current) {
                    start = k + 1;
                    break;
                }
                flag[arr[k]] = false;
            }
        } else {
            flag[current] = true;
        }
    }

    result = Math.max(arr.length - start, result);

    return result;
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n)