[ leetcode ] Longest Substring with At Most Two Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
最近のアルゴリズムは全く解けず,久しぶりにループコードを開いた.
まだ問題があります.
問題の説明は以下の通りです.
2つの文字だけからなる最長連続部分文字列の長さを求めます.
問題を見て、白俊回転寿司問題を思い出し、カトピラー法で解いた.
https://codility.com/media/train/13-CaterpillarMethod.pdf
以上のリンクは,この方法に関するpdfである.勉強すれば広く応用できる.
最近のアルゴリズムは全く解けず,久しぶりにループコードを開いた.
まだ問題があります.
Longest Substring with At Most Two Distinct Characters
問題の説明は以下の通りです.
2つの文字だけからなる最長連続部分文字列の長さを求めます.
問題を見て、白俊回転寿司問題を思い出し、カトピラー法で解いた.
https://codility.com/media/train/13-CaterpillarMethod.pdf
以上のリンクは,この方法に関するpdfである.勉強すれば広く応用できる.
import collections
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
start = 0
end = 0
letterCounter = collections.defaultdict(int)
letterKey = set()
answer = 0
cur_string = collections.deque([])
def addLetter(value):
letterCounter[value] += 1
letterKey.add(value)
def deleteLetter(value):
if letterCounter[value] == 1:
letterKey.remove(value)
letterCounter[value] -= 1
def isAddable(value):
return any([
value in letterKey and len(letterKey) <= 2,
value not in letterKey and len(letterKey) < 2
])
while (start < len(s) and end < len(s)):
if isAddable(s[end]):
addLetter(s[end])
cur_string.append(s[end])
answer = max(answer, len(cur_string))
end += 1
else:
deleteLetter(s[start])
cur_string.popleft()
start += 1
return answer
Reference
この問題について([ leetcode ] Longest Substring with At Most Two Distinct Characters), 我々は、より多くの情報をここで見つけました https://velog.io/@ha-mulan/leetcode-Longest-Substring-with-At-Most-Two-Distinct-Charactersテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol