Back to DSA
Longest Substring Without Repeating Characters
mediumGiven a string, determine the length of its longest contiguous segment that contains no repeated characters. Every character in the segment must be distinct.
Examples
Example 1:
Input:
s = "xyzxyzaa"Output:
3Explanation: The segment 'xyz' has length 3 and contains all unique characters. No longer valid segment exists.
Example 2:
Input:
s = "qqqqq"Output:
1Explanation: Every character is identical, so the longest segment without repetition has length 1.
Hints
import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int maxLen = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1);
}
map.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}Time complexity
O(n)Space complexity
O(min(m, n))