3 Longest Substring Without Repeating Characters
1. Question
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given"abcabcbb"
, the answer is"abc"
, which the length is 3.
Given"bbbbb"
, the answer is"b"
, with the length of 1.
Given"pwwkew"
, the answer is"wke"
, with the length of 3. Note that the answer must be a substring,"pwke"
is a subsequence and not a substring.
2. Implementation
(1) Two Pointer + Hash
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int maxLen = 0;
int start = 0, end = 0;
int count = 0;
int[] map = new int[256];
while (end < s.length()) {
if (map[s.charAt(end)] > 0) {
++count;
}
++map[s.charAt(end)];
++end;
while (count > 0) {
if (map[s.charAt(start)] > 1) {
--count;
}
--map[s.charAt(start)];
++start;
}
maxLen = Math.max(maxLen, end - start);
}
return maxLen;
}
}
3. Time & Space Complexity
Two Pointer + Hash: 时间复杂度O(n), 空间复杂度O(1)
Last updated
Was this helpful?