Longest Substring with At Most Two Distinct Characters (Leetcode 159) Solution - Top Google Interview Question

Mani
Mani
Educating everyone with the beauty of programming!!

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

Example 1:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

Example 2:

Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.

Constraints:

  • 1 <= s.length <= 104
  • s consists of English letters.

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
25
26
27
28
29
30
31
32
/**
 * Time Complexity: O(n)
 * Space Complexity: O(X) : X is the number of distinct characters in the input.
 */
class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> map = new HashMap<>();

        int max = 0;
        int l = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            Integer val = 1 + map.getOrDefault(ch, 0);
            map.put(ch, val);

            while (map.size() > 2 && l <= i) {
                char lchar = s.charAt(l);
                val = map.get(lchar) - 1;
                map.put(lchar, val);
                if (val == 0) {
                    map.remove(lchar);
                }
                l++;
            }

            max = Math.max(max, i - l + 1);
        }

        return max;
    }
}
Drop your comments below for any questions or comments. For full list of must learn top interview questions Click Here: Must Learn Top Interview Questions

Rating: