class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cnt = {}
f = 0
for i, n in enumerate(nums):
if n not in cnt:
cnt[n] = [1, i, i]
else:
c, a, _ = cnt[n]
cnt[n] = [c+1, a, i]
f = max(f, cnt[n][0])
return min(v[2]-v[1]+1 for v in cnt.values() if v[0]==f)


"00", "111", "00", "11"

"01", "0011"

class Solution(object):
def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
cnt = map(len, re.split('(0+)', s))
return sum(min(a, b) for a, b in zip(cnt[:-1], cnt[1:]))


class Solution(object):
def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
s = sum(nums)
if s % k != 0:
return False
s /= k
if max(nums) > s:
return False
nums.sort(key=lambda x: -x)

while nums:
dp = [-1] * (s+1)
dp[0] = 0
for n in nums:
for i in xrange(s, -1, -1):
if i + n <= s and dp[i] != -1 and dp[i+n] == -1:
dp[i+n] = i
if dp[s] != -1:
break
if dp[s] == -1:
return False
a = s
while a != 0:
nums.remove(a-dp[a])
a = dp[a]
return True


class Solution {
public:
vector<int> fallingSquares(vector<pair<int, int>>& positions) {
int n = positions.size();
vector<int> h(n, 0);
vector<int> ans(n, 0);
int c = 0;
for (int i = 0; i < n; i ++) {
int t = 0;
for (int j = 0; j < i; j ++)
if (overlap(i, j, positions))
t = max(t, h[j]);
t += positions[i].second;
c = max(c, t);
ans[i] = c;
h[i] = t;
}
return ans;
}
private:
bool overlap(int i, int j, vector<pair<int, int>>& p) {
int a = p[i].first;
int b = a+p[i].second;
int x = p[j].first;
int y = x + p[j].second;
return !(a >= y || x >= b);
}
};