Efficient Anagram Detection In O(n) Time And O(k) Space
Find anagrams in string s of length n and pattern p of length k. TC: O(n), SC: O(k) for substrings + O(1) for constant space array.
Problem
TC:O(n)
SC:(k) is no. of substrings(anagrams) + O(1) for using constant space array of size 26
class Solution {
public List<Integer> findAnagrams(String s, String p) {
Map<Character,Integer> map = new HashMap<>();
int arrp[] = new int[26];
for(int i = 0;i<p.length();i++) arrp[p.charAt(i)-'a']++;
int arrs[] = new int[26];
List<Integer> result = new ArrayList<>();
int left =0,right = 0;
while(right<s.length()){
if(right-left+1< p.length()){
arrs[s.charAt(right)-'a']++;
right++;...