Longest Substring Without Repeating Characters
LeetCode #3 · Medium · Sliding Window · C++ solution with worked-out approach and complexity analysis.
Approach
Sliding Window with Character Index Map
Use an array to store the last seen index of each character. Slide the window by moving left pointer when a repeat is found.
Time
O(n)
single pass through the string
Space
O(1)
fixed size array of 256 characters
Problem description(from LeetCode)
Given a string s, find the length of the longest substring without repeating characters.
Examples
Example 1
- Input:
- s = "abcabcbb"
- Output:
- 3
- Note:
- The answer is "abc", with the length of 3.
Example 2
- Input:
- s = "bbbbb"
- Output:
- 1
- Note:
- The answer is "b", with the length of 1.
Example 3
- Input:
- s = "pwwkew"
- Output:
- 3
- Note:
- The answer is "wke", with the length of 3.
Constraints
- •0 <= s.length <= 5 * 10^4
- •s consists of English letters, digits, symbols and spaces
C++ Solution
solution.cpp
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i = 0, res = 0;
vector<int> mp(256, -1);
for (int j = 0; j < s.length(); j++) {
if (mp[s[j]] != -1) {
i = max(i, mp[s[j]] + 1);
}
mp[s[j]] = j;
res = max(res, j - i + 1);
}
return res;
}
};