Tuesday, 16 July 2024

Two pointer approach in sliding window using hashmap

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

Solution:

Time complexity: in O(n)

import java.util.*;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new LinkedList<>();
        int n=s.length();
        HashMap<Character,Integer> s_mp=new HashMap<>();
        HashMap<Character,Integer> p_mp=new HashMap<>();
        for(int i=0;i<p.length();i++)
        {
            char c=p.charAt(i);
            p_mp.put(c,p_mp.getOrDefault(c,0)+1);
        }
        int i=0; int j=0;
        while(j<n)
        {
            char cs=s.charAt(j);
            s_mp.put(cs,s_mp.getOrDefault(cs,0)+1);
            if(j-i+1==p.length())
            {
                if(s_mp.equals(p_mp))
                {
                    result.add(i);
                }
            // Remove the character that's left behind as the window slides
            char leftChar = s.charAt(i);
            if (s_mp.get(leftChar) == 1) s_mp.remove(leftChar);
            else s_mp.put(leftChar, s_mp.get(leftChar) - 1);
                i+=1;
            }
            j+=1;
        }
        return result;
    }
}

Good thoughtful question on Binary search on answers

Problem link:  https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ Solution: //import java.util.Arrays; class So...