Skip to main content

[M] Longest Substring Without Repeating Characters

Đề bài

Cho một chuỗi s, hãy tìm độ dài của chuỗi con không chứa bất kỳ ký tự nào lặp lại.

Ví dụ:

Input: s = "abcabcbb"
Output: 3
Input: s = "bbbbb"
Output: 1
Input: s = "pwwkew"
Output: 3

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

Phân tích

Pseudocode

Solution

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
if (len < 2)
return len;

int left = 0, right = 0;
int longest = 0;
unordered_map<char, bool> map = {};
while (right < len) {
if (!map[s[right]]) {
map[s[right]] = true;
longest = max(longest, right - left + 1);
} else {
while (s[left] != s[right]) {
map[s[left]] = false;
left++;
}
left++;
}
right++;
}

return longest;
}
};