LC-2311 Medium LeetCode

2311. Longest Binary Subsequence Less Than or Equal to K

String Dynamic Programming Greedy Memoization

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 38% Topics: String, Dynamic Programming, Greedy, Memoization

Reading material

Strings 12 min 1-D Dynamic Programming 16 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

# greedy
class Solution(object):
    def longestSubsequence(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        result, base = 0, 1
        for i in reversed(xrange(len(s))):
            if s[i] == '0':
                result += 1
            elif base <= k:
                k -= base
                result += 1
            if base <= k:
                base <<= 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT