[LeetCode 2311] Longest Binary Subsequence Less Than or Equal to K

문제 바로가기

Description

---

You are given a binary string s and a positive integer k.

Return the length of the longest subsequence of s that makes up a binary number less than or equal to k.

Note:

• The subsequence can contain leading zeroes.
• The empty string is considered to be equal to 0.
• A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1

---

• Input: s = “1001010”, k = 5
• Output: 5
• Explanation:
  • The longest subsequence of s that makes up a binary number less than or equal to 5 is “00010”, as this number is equal to 2 in decimal.
  • Note that “00100” and “00101” are also possible, which are equal to 4 and 5 in decimal, respectively.
  • The length of this subsequence is 5, so 5 is returned.

Example 2

---

• Input: s = “00101001”, k = 1
• Output: 6
• Explanation:
  • “000001” is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
  • The length of this subsequence is 6, so 6 is returned.

Constraints

---

• 1 <= s.length <= 1000
• s[i] is either '0' or '1'.
• 1 <= k <= 10^9

Hint

---

Hint 1

  Choosing a subsequence from the string is equivalent to deleting all the other digits.
	

Hint 2

  If you were to remove a digit, which one should you remove to reduce the value of the string?
	

Code

---

내 제출

---

class Solution {
    public int longestSubsequence(String s, int k) {
        int ans = 0, v = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            if (s.charAt(i) == '0') {
                ++ans;
            } else if (ans < 30 && (v | 1 << ans) <= k) {
                v |= 1 << ans;
                ++ans;
            }
        }
        return ans;
    }
}

Runtime	Memory
1 ms	42.1 MB

다른 풀이

---

class Solution {
    public int longestSubsequence(String s, int k) {
        int zeros=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='0')zeros++;

        }

// We already counted all zeros in your first loop
for (int i = s.length() - 1; i >= 0; i--) {
    if (s.charAt(i) == '1') {
        int power = s.length() - 1 - i;
        
        // If the power is 30 or more, 2^power is > 10^9 (our k limit)
        if (power < 30) {
            int value = 1 << power; // This is 2^power
            if (value <= k) {
                k -= value;
                zeros++; // Using your variable name for the total count
            } else {
                break; // This '1' is too big, and any '1' to its left will be bigger
            }
        } else {
            break; // Exponent too large for k
        }
    }
}
        return zeros;
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2300-2399/2311.Longest%20Binary%20Subsequence%20Less%20Than%20or%20Equal%20to%20K/Solution.java