Leetcode 2311: Longest Binary Subsequence Less Than or Equal to K
You are given a binary string s and a positive integer k. Your task is to find the length of the longest subsequence of s that represents a binary number less than or equal to k when converted to decimal.
Problem
Approach
Steps
Complexity
Input: The input consists of a binary string s and an integer k.
Example: s = '1101011', k = 6
Constraints:
• 1 <= s.length <= 1000
• 1 <= k <= 10^9
• s[i] is either '0' or '1'.
Output: Return the length of the longest subsequence of s that forms a binary number less than or equal to k.
Example: For s = '1101011', k = 6, the output is 5.
Constraints:
• The subsequence should form a binary number less than or equal to k.
Goal: The goal is to find the longest subsequence of binary digits that represents a number less than or equal to k.
Steps:
• Start from the rightmost character in the string and traverse towards the left.
• Maintain a running total of the binary number formed and the length of the subsequence.
• For each '1', add its value to the running total and increment the subsequence length if the number is still less than or equal to k.
• Include all the '0's in the subsequence as they don't affect the binary value.
• Stop when you can no longer include '1's without exceeding k.
Goal: The problem constraints ensure that the string is manageable in size and contains only binary digits.
Steps:
• 1 <= s.length <= 1000
• 1 <= k <= 10^9
• s consists only of '0' and '1'.
Assumptions:
• The input string contains only '0's and '1's.
• Input: s = '1101011', k = 6
• Explanation: The longest subsequence of s that forms a binary number less than or equal to 6 is '00010', which is 2 in decimal. The length of the subsequence is 5.
Approach: To solve this problem, we need to find the longest subsequence of binary digits that does not exceed the value of k when converted to decimal.
Observations:
• We need to track both the length of the subsequence and the value of the binary number formed as we traverse the string.
• Starting from the least significant bit (rightmost), we can check whether adding the current '1' keeps the number within bounds.
Steps:
• 1. Initialize a variable to store the current binary number value and set it to 0.
• 2. Initialize a variable to store the subsequence length, starting at 0.
• 3. Traverse the string from right to left.
• 4. For each '1', check if adding it to the binary number keeps it within the limit k. If it does, update the value and increase the length.
• 5. Count all the '0's as part of the subsequence.
• 6. Return the total length of the subsequence.
Empty Inputs:
• The string will never be empty as per the problem constraints.
Large Inputs:
• Handle inputs of up to 1000 characters efficiently.
Special Values:
• If k is very large, ensure that we don't exceed it by adding bits.
Constraints:
• Ensure that the subsequence's value does not exceed k.
int longestSubsequence(string s, int k) {
int val = 0, cnt = 0, pow = 1;
for(int i = s.size() - 1; i >= 0 && val + pow <= k; i--) {
if(s[i] == '1') {
++cnt;
val += pow;
}
pow <<= 1;
}
return count(s.begin(), s.end(), '0') + cnt;
}
1 : Function Declaration
int longestSubsequence(string s, int k) {
Define the function `longestSubsequence` which takes a binary string `s` and an integer `k` as input. The function returns an integer representing the length of the longest subsequence whose binary value is less than or equal to `k`.
2 : Variable Initialization
int val = 0, cnt = 0, pow = 1;
Initialize three variables: `val` to store the current value of the selected binary digits, `cnt` to count the number of selected '1' digits, and `pow` to represent the current power of 2 for the binary number.
3 : For Loop
for(int i = s.size() - 1; i >= 0 && val + pow <= k; i--) {
Start a loop from the last character of the string `s` and move towards the beginning. Continue the loop as long as the current value `val` plus the next power of 2 does not exceed `k`.
4 : If Condition Check
if(s[i] == '1') {
Check if the current character in the string is '1'. If it is, include this '1' in the subsequence.
5 : Increment Count
++cnt;
Increment the counter `cnt` to account for the '1' that is selected as part of the subsequence.
6 : Update Value
val += pow;
Add the current power of 2 (`pow`) to the value `val` to update the total value of the subsequence.
7 : Shift Power of 2
pow <<= 1;
Shift the power of 2 (`pow`) left by 1 (equivalent to multiplying by 2) to account for the next bit in the binary number.
8 : Return Statement
return count(s.begin(), s.end(), '0') + cnt;
Return the sum of the count of '0' characters in the string `s` (using `count` function) and the count of '1' characters that were selected for the subsequence.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) where n is the length of the string, as we traverse the string once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we only use a constant amount of space to store the binary number value and subsequence length.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus