Longest Substring with At Most Two Distinct Characters
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 <= 105
s
consists of English letters.
Solution
Since we don't know the size of the window, we will apply the flexible sliding window template.
We will keep a last_occurrence
hashmap that stores the last occurence of a character in the current window.
Every time the right pointer reaches a new character, we update that character's last occurrence to r
.
In every iteration, we will check whether the current window is longer than max_len
.
This means that whenever the window becomes invalid, we must update the window first before the check.
We will update l
when condition(window)
evaluates to true
. Here, condition(window)
is when the hashmap contains three characters.
We must discard the entirety of one character c
, which means we will choose the smaller last_occurrence[c]
to maintain a longers substring.
So the new left pointer is updated to min(last_occurrence.values())+1
and we will delete this character from the last_occurrence
hashmap.
Implementation
1def lengthOfLongestSubstringTwoDistinct(self, s):
2 last_occurrence = dict()
3 max_len, l = 0, 0
4 for r in range(len(s)):
5 last_occurrence[s[r]] = r
6 r += 1
7 if len(last_occurrence) == 3:
8 l = min(last_occurrence.values())+1
9 del last_occurrence[s[l-1]]
10 max_len = max(max_len, r - l)
11 return max_len
How many times is a tree node visited in a depth first search?
Solution Implementation
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Recommended Readings
Patterns The Shortest Path Algorithm for Coding Interviews The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we can determine the
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.