Session 20: Hashing

Original Session

Date: 21 Dec 2024

Topic: Two Pointers & HashMap

Programs

1. 387. First Unique Character in a String
   1. leetcode here

   public int firstUniqChar(String s) {
           
           Map<Character, Integer> map = new HashMap();
           char[] chA = s.toCharArray();
   
           for (char c: chA) {
   
               map.put(c, map.getOrDefault(c, 0) + 1);
           }
   
           for (int i=0; i< chA.length; i++) {
   
               if(map.get(chA[i]) == 1) {
                   return i;
               }
           }
           
           return -1;
       }

2. 340. Longest Substring with At Most K Distinct Characters
   1. leetcode here

   static int longestSubstring(String s, int k) {
           
           int left = 0;
           int right = 0;
           int ans = 0;
           char[] chArray = s.toCharArray();
           Map<Character, Integer> map = new HashMap();
           
           while (right < chArray.length) {
               
               map.put(chArray[right], map.getOrDefault(chArray[right], 0) + 1);
               
               while (map.size() > k) {
                   map.put(chArray[left], map.getOrDefault(chArray[left], 0) - 1);
                   
                   if (map.getOrDefault(chArray[left], -1) == 0) {
                       map.remove(chArray[left]);
                   }
                   
                   left ++;
               }
               
               ans = Math.max(ans, right-left+1);
               
               right ++;
           }
           
           return ans;
       }

3. 930. Binary Subarrays With Sum
   1. leetcode here

   public int numSubarraysWithSum(int[] nums, int goal) {
           
           int left = 0, right = 0;
           int sum = 0, prefixSum = 0, ans = 0;
   
           while (right < nums.length) {
   
               sum += nums[right];
   
               while (left < right && (nums[left] == 0 || sum > goal)) {
   
                   if (nums[left] == 0) {
                       prefixSum ++;
                   } else {
                       prefixSum = 0;
                   }
   
                   sum -= nums[left];
                   left++;
               }
   
               if (sum == goal) {
                   ans += 1 + prefixSum;
               }
   
               right++;
           }
           return ans;
       }

4. 992. Subarrays with K Different Integers
   1. leetcode here

   public int subarraysWithKDistinct(int[] nums, int k) {
           
           return atmost(nums, k) - atmost(nums, k-1);
   
       }
   
       int atmost(int[] nums, int k) {
           
           Map<Integer, Integer> map = new HashMap();
           int left = 0, ans = 0;
   
           for (int right = 0; right < nums.length; right ++) {
   
               map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
   
               while (map.size() > k) {
   
                   map.put(nums[left], map.getOrDefault(nums[left], 0) - 1);
                   if (map.getOrDefault(nums[left],0) == 0) {
                       map.remove(nums[left]);
                   }
   
                   left ++;
               }
   
               ans = ans + (right-left+1);
           }
   
           return ans;
   
       }

5. [HomeWork] 1248. Count Number of Nice Subarrays
   1. leetcode here

6. [HomeWork] 76. Minimum Window Substring
   1. leetcode here