LC: 159. Longest Substring with At Most Two Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
159. 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.
Longest Substring with At Most Two Distinct Characters
The Essence:
Wenn ein Teilstring aus zwei Zeichen besteht und eine neue Teilzeichenfolge mit einem dritten Zeichen zugefügt wird, ist die Länge der nächsten Teilzeichenfolge mit zwei unterschiedlichen Zeichen die Länge der Teilzeichenfolge, die aus der Teilfolge mit dem letzten Zeichen im Vorherigen und dem neuen Zeichen besteht.
"abbabb" + "c" -> "bbc"
Um in einem solchen Fall die gesuchte Länge zu berechnen, muss der Algorithmus also den Index des ersten Zeichens sowie den Index des zweiten Zeichens speichern. Die Länge kann durch Umordnen der Indizes berechnet werden.
Details:
Zwei Zeiger a und b, die das letzte Vorkommen der beiden Zeichen im Index speichern, sind ausreichend. Die verarbeitete Länge wird inkrementiert, solange die beiden Zeichen wieder auftreten. Wenn ein drittes Zeichen vorkommt, sollte das mit dem neuesten Index für die neue verarbeitete Länge gezählt werden.
Solution(s) and Further Explanation:
Default Code:
Last updated