Longest Substring Without Repeating Characters (Leetcode 3) Solution - Top Google, Amazon Interview Question
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.
Example 4:
Input: s = "" Output: 0
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Time Complexity: O(n)
* Space Complexity: Unique Chracters of the string.
*
* The key is l = Math.max(map.get(ch) + 1, l);
* If a character is already present then we shift the left pointer to the latest of l or the next
* index of last occurance of ch.
*/
class Solution {
public int lengthOfLongestSubstring(String s) {
int l = 0;
int max = 0;
Map<Character, Integer> map = new HashMap<>();
for (int r = 0; r < s.length(); r++) {
char ch = s.charAt(r);
if (map.containsKey(ch)) {
l = Math.max(map.get(ch) + 1, l);
}
map.put(ch, r);
max = Math.max(max, r - l + 1);
}
return max;
}
}