Interviews

Find All Anagrams

user profile image
System made a post.

Find the indices of all anagrams of a given word in a another word.
For example: Find the indices of all the anagrams of AB in ABCDBACDAB
(Answer: 0, 4, 8)


public static List getAnagrams(String s, String word) {
    Map letters = new HashMap<>();
    int distinct_letters = 0;
    for (char c : word.toCharArray()) {
        if (!letters.containsKey(c)) distinct_letters++;
        letters.put(c, letters.getOrDefault(c, 0) + 1);
    }

    //search for anagrams with two pointers
    List res = new ArrayList<>();
    int lo = 0, hi = 0;
    while (hi < s.length()) {
        if (!letters.containsKey(s.charAt(hi))) {
            while (lo < hi) {
                char c = s.charAt(lo);
                if (letters.get(c) == 0) distinct_letters++;
                letters.put(c, letters.get(c) + 1);
                lo++;
            }
            hi++;
            lo = hi;
        } else if (letters.get(s.charAt(hi)) == 0) {
            char c = s.charAt(lo);
            if (letters.get(c) == 0) distinct_letters++;
            letters.put(c, letters.get(c) + 1);
            lo++;
        } else {
            char c = s.charAt(hi);
            letters.put(c, letters.get(c) - 1);
            if (letters.get(c) == 0) distinct_letters--;
            if (distinct_letters == 0) {
                res.add(lo);
            }
            hi++;
        }
    }
    return res;
}


One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview

Get one-to-one training from Google Facebook engineers


Top-notch Professionals

Learn from Facebook, Google, Uber senior engineers interviewed 100+ candidates.aonecode.com
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.


Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.


Free Consultation

aonecoding@gmail.com