LC: 340. Longest Substring with At Most K Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
340. Longest Substring with At Most K Distinct Characters
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.Constraints:
1 <= s.length <= 5 * 1040 <= k <= 50
Longest Substring with At Most K Distinct Characters
The Essence:
Wenn ein Zeichen zu einer Teilzeichenfolge zugefügt wird und die Teilzeichenfolge damit k+1 verschiedene Zeichen hat, dann sollte die linke Grenze dieser Teilzeichenfolge verkleinert werden, bis die Anzahl eines anderen Zeichens in der Teilzeichenfolge 0 erreicht. Danach kann das Verfahren vergleichen und versuchen, ein neues Zeichen zuzufügen(die rechte Grenze erweitern).
Details:
Für die Implementierung reicht es aus, einfach ein Array oder eine Tabelle zum Anzahl der Zeichen zu haben. Es sollte auch einen linken und rechten Index geben, um Teilzeichenfolge darzustellen. Die aktuelle Anzahl der unterschiedlichen Zeichen sollte ebenfalls gespeichert werden. Die Verwendung von linken und rechten Indizes ist eine wichtige Technik bei Array- und Stringproblemen. Die Problemlöser sollen versuchen, sich mit solchen Techniken bekannt zu machen. Andere ähnliche Algorithmen-Probleme können dabei hilfreich sein.
Solution(s) and Further Explanation:
Further explanation and the code implementation can be found here:
Default Code:
Last updated