MrainW's Home

All things come to those who wait!

0%

LeetCode 159. Longest Substring with At Most Two Distinct Characters

Question

Given a string s, return the length of the longest substring that contains at most two distinct characters.

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

  • Solution1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
Map<Character, Integer> map = new HashMap<>();
int left = 0, res = 0;
for (int i = 0; i < s.length(); i++){
//renew current character
char cur = s.charAt(i);
map.put(cur, map.getOrDefault(cur, 0) + 1);
//加条件,不符合的从left移除
while (map.size() > 2){
char c = s.charAt(left);
map.put(c, map.get(c) - 1);
if (map.get(c) == 0) map.remove(c);
left++;
}
res = Math.max(res, i - left + 1);
}
return res;
}
}

Complexity:

Time complexity: O( n)

Space complexity: O(n)

Welcome to my other publishing channels