LeetCode 2554: Maximum Number of Integers to Choose From a Range I

Explanation

To solve this problem, we can iterate through the range [1, n] and check if the current integer is not in the banned array and adding it to the sum still keeps the sum within maxSum. We can use a HashSet to efficiently check if an integer is in the banned array. By iterating through the range and applying these conditions, we can find the maximum number of integers that can be chosen. We need to keep track of the maximum number of integers chosen so far and return that as the result.

• Time complexity: O(n) where n is the range of integers [1, n]
• Space complexity: O(m) where m is the size of the banned array

import java.util.HashSet;

class Solution {
    public int maxNumOfSubstrings(String s) {
        HashSet<Integer> bannedSet = new HashSet<>();
        for (int b : banned) {
            bannedSet.add(b);
        }

        int maxCount = 0;
        for (int i = 1; i <= n; i++) {
            if (!bannedSet.contains(i) && i <= maxSum) {
                maxCount++;
                maxSum -= i;
            }
        }

        return maxCount;
    }
}