# Python greedy via sorting by length.

• The key idea is sort the elements in strs by their length. When there is a tie, choose one with smaller difference between the number of "0" and "1" to be the preferable choice.

``````class Solution(object):
def findMaxForm(self, strs, m, n):
"""
:type strs: List[str]
:type m: int
:type n: int
:rtype: int
"""
A = sorted(strs, key = lambda x : (len(x), - x.count("0") * x.count("1")))
ans = 0
for i in A:
M, N = i.count("0"), i.count("1")
if M <= m and N <= n:
ans += 1
m -= M
n -= N
return ans
``````

• This method happens to pass all test cases, but what is the proof for why this greedy selection method works in all cases?

• @compton_scatter
Exactly, counter-example:
`["1100","100000","011111"]`
`6`
`6`

• ["0011", "0001", "0111"]
4
4

• Thanks @70664914 and @在线疯狂, I have added both of your test cases.

• Made a mistake during validation process, thanks for your correctness, will be more careful next time when dealing with greedy stuff. @在线疯狂 @70664914

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.