class Solution { // Method to calculate distinct sub-array static int countDistinctSubarray(int arr[], int n) { //similiar to previous question //finding total unique numbers HashSet<Integer> set = new HashSet<>(); for(int val : arr) set.add(val); int k = set.size(); //exactly k strings = atmost(k) - atmost(k-1) return atmostK(arr , k) - atmostK(arr,k-1); } //finding atmost(k) strings static int atmostK(int arr[] , int k){ int ans = 0; int j = 0; HashMap<Integer,Integer> map = new HashMap<>(); for(int i = 0 ;i < arr.length ; i++){ int val = arr[i]; map.put(val , map.getOrDefault(val,0)+1); while(map.size() > k){ int temp = arr[j]; if(map.get(temp) == 1) map.remove(temp); else map.put(temp , map.get(temp)-1); j++; } //adding all subtrings ans += i-j+1; } return ans; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter