Count occurrence of anagrams in String



















We would be solving this problem using 
  • Sliding Window approach with 1 Hashmap
  • First we will populate pattern map with occurrence of chars in pattern map.
  • Additionally, a new indicator distinctCharsInMapValueMoreThanZero will be created. It's initial value would be map.size(). This variable is for numbers of chars in map with value > 0. This will ensure we don't have to compare all values of map to see, if all characters are zero or not.
  • When variable distinctCharsInMapValueMoreThanZero is zero, it means current substring is anagram of pattern. 
  • When traversing string via Sliding window, we will keep reduce count of character in pattern map.
  • In map, we will not push any char, which are not part of pattern.

Comments

Post a Comment

Popular posts from this blog

Sliding Window Maximum (Maximum of all subarrays of size k) - Java Solution - Leetcode 239

Image
Solution approach : We will be using sliding window. Deque will be used to store useful element of current subarray. Add first element to deque. Then for adding next element, check if earlier elements are smaller, then remove all elements from deque. Maximum will always be at front of deque. For sliding and removing, check if arr[i] == front of queue, then remove the element. import java.util.Arrays ; import java.util.Deque ; import java.util.LinkedList ; public class MaxOfAllSubarrays { private static int [] findMaxOfAllSubArrays ( int [] arr , int subArraySize) { int [] answerArr = new int [arr. length - subArraySize + 1 ] ; int i = 0 , j = 0 , count = 0 ; Deque<Integer> deque = new LinkedList<>() ; while (j < arr. length ) { while (!deque.isEmpty() && deque.getLast() < arr[j]) deque.removeLast() ; deque.add(arr[j]) ; if (j - i + 1 == subArraySize) { answe...
Read more
 Shell Sort Implementation program in Java https://github.com/cbsingh1/DailyCodingProblems/blob/main/src/main/java/com/cbsingh/sorting/ShellSortImpl.java
Read more