-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongSubWORepChar.java
More file actions
67 lines (54 loc) · 1.96 KB
/
LongSubWORepChar.java
File metadata and controls
67 lines (54 loc) · 1.96 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.*;
class LongSubWORepChar {
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char currentChar = s.charAt(right);
// If currentChar is a dup in the window, move left
if (map.containsKey(currentChar)) {
left = Math.max(left, map.get(currentChar) + 1);
}
// Update the char's laatest index
map.put(currentChar, right);
// Calc max length of the current window
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
public static void main(String[] args) {
String s = "abcabcbb"; // 3
System.out.println(lengthOfLongestSubstring(s));
}
}
/*
Sliding window
- 2 pointers, left and right, to represent the current window
- Expand the right pointer to include new chars
- If a duplicate is found, move the left pointer to the right of the last
occurrence of the dup char to remove it from the window
Use a HashMap to Track Chars
- Use a hash to store the most recent index of each char
- If a char is already in the map (indicating a dup in the window),
move the left pointer to map.get(char) + 1 to skip over the prev occurrence
Updated the Max Length
- After each addition of a char to the window, calc the length of the
current substring as right-left+1
* Given a string s, find the length of the longest
substring
without repeating 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.
*/