904. Fruit Into Baskets

• 904. Fruit Into Baskets
  • Description
  • Intuition
  • Pitfall
  • Solution
  • Reference

Description

Here

Intuition

这题很容易想到slide window，但其实这题有更鸡贼的方法

考虑到bucket顶多放两个字母，如果碰到了一个char c, 如果在之前bucket里的，那么可以继续count; 如果不在，只需要tracking之前最后一次连续的char的count就行了

举个例子，...aaaaaabbbbbc...,哪怕b之前出现过很多回，那么也只是最后一回的matters

Explanation: Loop all fruit c in tree, Note that a and b are the last two different types of fruit that we met, c is the current fruit type, so it's something like "....aaabbbc..."

Case 1 c == b: </p> fruit c already in the basket, and it's same as the last type of fruit cur += 1 count_b += 1

Case 2 c == a:</p> fruit c already in the basket, but it's not same as the last type of fruit cur += 1 count_b = 1 a = b, b = c

Case 3 c != b && c!= a:</p> fruit c not in the basket, cur = count_b + 1 count_b = 1 a = b, b = c

Of course, in each turn we need to update res = max(res, cur)

Pitfall

Solution

Reference

Leetcode Discuss