Longest Substring Without Repeating Characters

MEDIUM

Description

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 10⁴
s consists of English letters, digits, symbols and spaces.

Approaches

Checkout 3 different approaches to solve Longest Substring Without Repeating Characters. Click on different approaches to view the approach and algorithm in detail.

Brute Force

This approach checks every possible substring to see if it contains unique characters and keeps track of the maximum length found.

Algorithm

Initialize maxLength = 0.
Use a loop with index i from 0 to s.length() - 1 to select the starting character of the substring.
Use a nested loop with index j from i to s.length() - 1 to select the ending character of the substring.
For each substring s.substring(i, j + 1), check if all its characters are unique.
To check for uniqueness, use a HashSet. Iterate from i to j, adding s.charAt(k) to the set. If a character is already present, the substring has duplicates.
If the substring has unique characters, update maxLength = Math.max(maxLength, j - i + 1).
After all substrings are checked, return maxLength.

The brute-force method involves generating all substrings of the given string s. For each substring, we then verify if it contains any duplicate characters.

To generate all substrings, we use two nested loops. The outer loop fixes the starting index i, and the inner loop fixes the ending index j.

For each substring from i to j, a helper function is used to check for uniqueness. This function typically uses a HashSet to store characters of the current substring. If a character is encountered that is already in the set, the substring is not unique. Otherwise, if the entire substring is traversed without finding duplicates, it's valid, and we update our maximum length.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (allUnique(s, i, j)) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }

    private boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i <= end; i++) {
            char ch = s.charAt(i);
            if (set.contains(ch)) {
                return false;
            }
            set.add(ch);
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n³)Space Complexity: O(min(n, m)) where n is the length of the string and m is the size of the character set.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Highly inefficient due to its cubic time complexity.
Redundant computations as it re-evaluates overlapping substrings multiple times.

Code Solutions

Checking out 5 solutions in different languages for Longest Substring Without Repeating Characters. Click on different languages to view the code.

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        var ss = new HashSet < char > ();
        int i = 0, ans = 0;
        for (int j = 0; j < s.Length; ++j) {
            while (ss.Contains(s[j])) {
                ss.Remove(s[i++]);
            }
            ss.Add(s[j]);
            ans = Math.Max(ans, j - i + 1);
        }
        return ans;
    }
}

Video Solution

Watch the video walkthrough for Longest Substring Without Repeating Characters

Patterns:

Sliding Window

Data Structures:

Hash TableString

Companies:

AMD |Accenture |Accolite |Adobe |