[LeetCode] 1288. Remove Covered Intervals

 Problem : https://leetcode.com/problems/remove-covered-intervals/

Steps:

- Sort intervals by its beginning point in ascending order. If beginning point are the same, sort by ending point in descending order.

- Iterate all intervals.  If one interval cannot extend current ending point to further position, then it is covered and can be removed.

Time complexity = O ( N * Log(N) ) + O ( N )

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        int result = intervals.length;
        
        int rightSoFar = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][1] <= rightSoFar) {
                result -= 1;
            } else {
                rightSoFar = intervals[i][1];
            }
        }
        
        return result;
    }
}

[LeetCode] 438. Find All Anagrams in a String

 Problem : https://leetcode.com/problems/find-all-anagrams-in-a-string/

Use sliding window approach. 

Time complexity =  O (M) + O (N). M = length of s. N = length of p.

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        Map<Character, Integer> counter = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            counter.put(p.charAt(i), counter.getOrDefault(p.charAt(i), 0) + 1);
        }
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            counter.put(s.charAt(right), counter.getOrDefault(s.charAt(right), 0) - 1);
            while(left <= right && counter.get(s.charAt(right)) < 0) {
                counter.put(s.charAt(left), counter.get(s.charAt(left)) + 1);
                left += 1;
            }

            if (right + 1 - left == p.length()) {
                result.add(left);
            }
        }

        return result;
    }
}

Updated on 02/05/2023. Updated for a simplier sliding window solution which uses one hashmap to record the enoutered needed letters.