Longest Substring Without Repeating Characters
MedPrompt
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 * 104sconsists of English letters, digits, symbols and spaces.
Approaches
3 approaches with complexity analysis and trade-offs.
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
ifrom0tos.length() - 1to select the starting character of the substring. - Use a nested loop with index
jfromitos.length() - 1to 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 fromitoj, addings.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.
Walkthrough
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
Time
O(n³)
Space
O(min(n, m)) where n is the length of the string and m is the size of the character set.
Trade-offs
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.
Solutions
Solution
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 walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.