CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN (recommended for candidates of FB, LinkedIn, Amazon, Google and Uber etc.),
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our members got offers from G, U, FB, Amazon, LinkedIn, Twitter and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION

public static List<Integer> getAnagrams(String s, String word) {
        Map<Character, Integer> 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<Integer> 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;
    }

Using hashing - O(m+n)

public static void main(String args[]) {
        String a = "AB";
        String b = "ABCDBACDAB";
        indices(a, b);
    }
    
    public static void indices(String a, String b){
        double hash = hash(a);
        int n = b.length();
        for(int i = 0; i < n-a.length()+1; i++){
            String s = b.substring(i, a.length()+i);
            double h = hash(s);
            if(h == hash)
                System.out.print(i + " ");
        }
    }
    
    public static double hash(String str){
        int n = str.length();
        double k = 9.3451;
        double h = 0;
        for(int i = 0; i < n; i++)
            h += str.charAt(i)*k;
        return h;
    }

Using hashing - O(m+n)

public static void main(String args[]) {
        String a = "AB";
        String b = "ABCDBACDAB";
        indices(a, b);
    }
    
    public static void indices(String a, String b){
        double hash = hash(a);
        int n = b.length();
        for(int i = 0; i < n-a.length()+1; i++){
            String s = b.substring(i, a.length()+i);
            double h = hash(s);
            if(h == hash)
                System.out.print(i + " ");
        }
    }
    
    public static double hash(String str){
        int n = str.length();
        double k = 9.3451;
        double h = 0;
        for(int i = 0; i < n; i++)
            h += str.charAt(i)*k;
        return h;
    }

vector<int> AnagramIndexes(string const &s, string const &small_s)
{
	vector<int> out;
	if (!small_s.empty() &&
		small_s.size() <= s.size())
	{
		vector<int> char_counts;
		char_counts.resize(256, 0);
		for (char c : small_s) {
			++char_counts[c];
		}
		int diffs_count = small_s.size();
		for (int i = 0; i < s.size(); ++i) {
			--char_counts[s[i]];
			diffs_count += char_counts[s[i]] < 0 ? 1 : -1;
			if (i >= small_s.size()) {
				++char_counts[s[i - small_s.size()]];
				diffs_count += char_counts[s[i - small_s.size()]] > 0 ? 1 : -1;
			}
			if (diffs_count == 0) {
				out.push_back(i - small_s.size() + 1);
			}
		}
	}
	return out;
}

Easy solution with complexity O(mnlogm). Can be improved if instead of using sort you use a more complex approach - use hashing or a Map of letters.

package com.careercup.ruslanbes.q5683479172874240;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class Main {

    public static int[] findAnagrams(String needle, String stack) {
        List<Integer> anagrams = new LinkedList<>();

        char[] needleDict = getDict(needle);
        int m = needle.length();
        int n = stack.length();
        for(int i = 0; i < n-m+1; i++){
            char[] stackDict = getDict(stack.substring(i, i+m));
            if (Arrays.equals(needleDict, stackDict)) {
                anagrams.add(i);
            }
        }

        return listToArray(anagrams);
    }

    protected static char[] getDict(String s) {
        char[] sDict = s.toCharArray();
        Arrays.sort(sDict);
        return sDict;
    }

    protected static int[] listToArray(List<Integer> list) {
        int[] array = new int[list.size()];
        for(int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }
        return array;
    }
}

How about like this

import java.util.Set;
import java.util.TreeSet;

public class AnagramsIndices {

	public static void main(String[] args) {
		finder("AB", "ABCDBACHSGAB");
		finder("ABC", "ABCDBACHSGAB");
		finder("DABC", "ABCDBACHSGAB");
	}
	
	static void finder(String pattern, String exp){
		int patLen = pattern.length();
		int expLen = exp.length();
		char space = ' ';
		Set<Integer> indices = new TreeSet<Integer>();
		
		for(int i = 0 ; i <= (expLen-patLen); i++){
			String localExp = exp.substring(i, i+patLen);
			char[] charArray = pattern.toCharArray();
			int counter = 0;
			for(char singleChar : charArray){
				if(localExp.contains(String.valueOf(singleChar))){
					localExp.replace(singleChar, space);
					counter ++;
				}else{
					break;
				}
				if(counter == patLen)
				indices.add(i);
			}
			counter = 0;
		}
		System.out.println(indices.toString());
	}
}

How can i find out it's complexity ?

def histogram(s):
fm = {}
for c in s:
fm[c] = fm.get(c, 0) + 1
return fm

def find_ana_indices(hays, needle):
fneedle = histogram(needle)
for i in range(len(hays) - len(needle) + 1):
if histogram(hays[i:i+len(needle)]) == fneedle:
print i

find_ana_indices('abcdbacb', 'abc')

def histogram(s):
    fm = {}
    for c in s:
        fm[c] = fm.get(c, 0) + 1
    return fm

def find_ana_indices(hays, needle):
    fneedle = histogram(needle)
    for i in range(len(hays) - len(needle) + 1):
        if histogram(hays[i:i+len(needle)]) == fneedle:
            print i

find_ana_indices('abcdbacb', 'abc')

Use KMP algorithm

The best solution for this problem is use KMP algorithm