Back to Sliding Window
Medium
Longest Substring Without Repeating Characters
Given a string `s`, find the length of the longest substring without repeating characters.
Examples
Input:s = "abcabcbb"
Output:3
The answer is "abc", with the length of 3.
Input:s = "bbbbb"
Output:1
The answer is "b", with the length of 1.
Constraints
0 <= s.length <= 5 * 10^4s consists of English letters, digits, symbols and spaces.
Approach
Generate all possible substrings using two nested loops. For each substring, iterate through it to check if there are any duplicate characters using a hash set. Keep track of the maximum length of a substring that does not have any duplicates.
Complexity Analysis
Time Complexity
O(n^3)
Space Complexity
O(min(m, n))
This approach is very slow and will likely cause Time Limit Exceeded (TLE) on large strings.
Solution.java
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int res = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (checkRepetition(s, i, j)) { res = Math.max(res, j - i + 1); } } } return res; } private boolean checkRepetition(String s, int start, int end) { Set<Character> chars = new HashSet<>(); for (int i = start; i <= end; i++) { char c = s.charAt(i); if (chars.contains(c)) { return false; } chars.add(c); } return true; }}