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 <= 105sconsists 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
Which of these properties could exist for a graph but not a tree?
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
Solution Implementation
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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 Teaching 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.