Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

340. Longest Substring with At Most K Distinct Characters (Leet Code, Google)

LeetCode 尺取り法 就活 Google

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

problems

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

note

I used "shakutoriho". Firstly, I check the 's' string from the head to the end with right iterator. I can save the information whether I found the character in hash map. When I found the new character, I increment the count of the distinct numbers. If I found the character which I already had found, I can proceed the left iterator and decrement the count of the distinct numbers. Through this manipulation, if the situation is max numbers of the distinct num > k, I can save the max difference between right iterator and left iterator. It means the max length substring I wanna get.

code