Both questions were renamed versions of existing LeetCode problems. Neither was particularly difficult overall; if you're quick with implementation and edge cases, you can finish within 30 minutes:
Q1: Count Binary Substrings
- LeetCode problem: LC 696, Count Binary Substrings (Easy).
- Topics: Two pointers / counting adjacent runs, or run-length encoding.
- Approach: Count the lengths of consecutive runs of 0s and 1s. Add the smaller length for each pair of adjacent runs. Remember to add the final pair after the scan. You can get the time and space complexity down to O(N) and O(1).
Q2: Maximize Score
- LeetCode problem: LC 740, Delete and Earn (Medium).
- Topic: Dynamic programming, a variation on House Robber.
- Approach: Choosing v means deleting v-1 and v+1. Count the total gain for each value, v * count[v], then use a DP that cannot select adjacent values: dp[i] = max(dp[i-1], dp[i-2] + gain[i]). If the upper limit of the value range is large, I'd suggest sorting the distinct keys and using a sparse DP.
Discussion
Loading comments…