CareerCup

1. Create the hash map of the characters of s1
2. Initialize the counter to 0
3. Iterate over S2 in the way:
- if current character in HashMap then counter++
- otherwise counter = 0
4. Stop when counter == HashMap.size()

Try rolling hash. (Rabin karp)

The basic idea is to use a map to count the number of characters in string1, and then use another map to track the number of occurances in string2. And use count to check if we have satisfied the conclusion.

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Solution{
	public List<Integer> findIndex(String s1, String s2){
	    Map<Character, Integer> map = new HashMap<Character, Integer>();
	    List<Integer> resultList = new LinkedList<Integer>();
	    //put all characters in a map
	    for(int i = 0; i < s1.length(); ++i){
	        char c = s1.charAt(i);
	        if(!map.containsKey(c)){
	            map.put(c, 1);
	        }else{
	            map.put(c, map.get(c) + 1);
	        }
	    }
	    int count = 0;
	    Map<Character, Integer> tempMap = new HashMap<Character, Integer>();
	    for(int i = 0; i < s2.length(); ++i){
	        char c = s2.charAt(i);
	        if(!map.containsKey(c)){
	            count = 0;
	            tempMap.clear();
	        }else{
	        	//for cases like s1 = "abcd", "abcda"
	        	if(count == s1.length()){
	        		char cc = s2.charAt(i - s1.length());
	        		tempMap.put(cc, tempMap.get(cc) - 1);
	        		--count;
	        	}
	            if(!tempMap.containsKey(c)){
	                tempMap.put(c, 1);
	            }else{
	                tempMap.put(c, tempMap.get(c) + 1);
	            }
	            if(tempMap.get(c) <= map.get(c)){
	                ++count;
	                if(count == s1.length()){
	                    resultList.add(i - s1.length() + 1);
	                }
	            }else{
	                count = 0;
	                tempMap.clear();
	            }
	        }
	    }
	    return resultList;
	}
	
	public static void main(String[] args){
		Solution s = new Solution();
		System.out.println(s.findIndex("aa", "abcdefcdbacd"));
	}
}

#include<iostream>
#include<string>
#include<list>
#include<vector>
using namespace std;
string makeperm(string str,char i,int pos)
{str.insert(pos,1,i);

return str;
}
list<string>gen_perm(string str)
{list<string>perm;
if(str.empty())
{perm.push_back(string(1,' '));return perm;}

perm.push_back(string(1,str[0]));list<string>temp;
for( int i=1;i<str.length();i++)
{
for(string j:perm)
{
for(int k=0;k<=j.length();k++)
{
string nextperm=makeperm(j,str[i],k);
temp.push_back(nextperm);
}

}perm.clear();
for(string h: temp)perm.push_back(h);temp.clear();
}

return perm;
}
vector<int> finanagrm(string s1,string s2)
{
list<string>perm=gen_perm(s1);vector<int>indx;int len=s1.length();
for(int i=0;i<=s2.length()-s1.length();i++)
{
for(string wrd :perm)
{
if(s2.substr(i,len)==wrd)
{indx.push_back(i);
break;}
}
}
return indx;
}
main()
{vector<int>angrmind=finanagrm("abcd","abcdefcdabcd");
for(int i:angrmind)cout<<i<<endl;

}

Here is simple C function to return string s2 index in s1

int strpos(char s1[],char s2[])
{
int i,j1,j2;
int len1,len2;
len1=strlen(s1);
len2=strlen(s2);
for (i=0; (i+len2)<len1; i++)
for(j1=i,j2=0; (j2<len2 )&& (s1[j1]==s2[j2]) ; j1++, j2++)
;
if ((i+1)==j2)
return i;
}

you can find this by using rolling hash. Code in C#:

public void FindAnagram(string strText, string strPattern)
        {
            int patternL = strPattern.Length;
            int textL = strText.Length;
            int Quad = 13; // Take prime number for better result
            int patternHash = HashFunction(strPattern, patternL, Quad,0);
            int textHash = HashFunction(strText, patternL, Quad,0);

            for (int i = 0; i < textL - patternLength + 1; i++)
            {
                //Check whether the exact matching pattern and text
                textHash = HashFunction(strText, patternL, Quad, i);
                if (patternHash == textHash && VerifyString(strText, i))
                    Console.WriteLine(i);
            }
        }

        private int HashFunction(string text, int patternL, int Quad, int offset)
        {
            int hashVal = 0, sum =0;

            for (int i = 0; i < patternL; i++)
                sum = sum + text[offset + i];

            hashVal = (10 * hashVal + sum) % Quad;
            return hashVal;
        }

        private bool VerifyString(string text, int offset)
        {
            string sliceSort = SortString(text.Substring(offset, patternLength));
            string patternSort = SortString(Pattern);
            for (int i = 0; i < patternLength; i++)
            {
                if (patternSort[i] != sliceSort[i])
                    return false;
            }
            return true;
        }

        static string SortString(string s)
        {
            // Convert to char array, then sort and return
            char[] a = s.ToCharArray();
            Array.Sort(a);
            return new string(a);
        }

Here is my solution in C++, anagram function takes complexity n*m and the other liner.

#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
bool isAnagram(string s1,string s2)
{
	int s_IT;
	if ( s1.length() != s2.length()) return false;
	for(int i = 0; i < s1.length(); i++)
	{
		s_IT = s2.find(s1[i]);
		if(s_IT == string::npos) return false;
		else			
			s2.erase(s_IT,1);
	}	
	return s2.empty();
}

void findInd(string s2,string s1)
{
	int len = s1.length();
	for(int i = 0; i < s2.length() - len + 1; i++)
	{
		string s3 = s2.substr(i,len);	
		if (isAnagram(s3,s1))
			cout << i <<endl;	
	}

}

int _tmain(int argc, _TCHAR* argv[])
{
	string s1 = "abcd";
	string s2 = "abcdefcdbacd";
	findInd(s2,s1);
	return 0;
}

int main(){
	bool char_map[26] = {0};
	char *s1 = "abcd";
	char *s2 = "acdbfecdabcd";
	int start = -1;
	int length = strlen(s1);
      	for(int i = 0; s1[i]; ++i) char_map[s1[i] - 'a'] = true;
	
	for(int i = 0; s2[i]; ++i){
		if(s1[s2[i]-'a']) ++count;
		else{count = 0; start = i;}
		if(count == length){
			print("%d ", start);
			start = i;		
		}
	}
}

o(n) solution.
Assume all the characters are lowercase alphabet. int in java is 32 bit and there are just 26 alphabet. So we have one bit for each alphabet.

Create a num by setting its corresponding bit from str2. x = x | 1<< (a[i] -'a')

Now for wah window of str2.length, find the same number and check if the numbers are same.

Window can move one character one by one.

bool areAnagrams(string const &s1, string const &s2)
{
	string str1(s1), str2(s2);
	sort(str1.begin(), str1.end());
	sort(str2.begin(), str2.end());
	return str1 == str2;
}
vector<size_t> FindSubString(string const &s1, string const s2)
{
	vector<size_t> result;
	for (size_t i = 0; i < s1.size(); i++) {
		if (areAnagrams(s1.substr(i, s2.size()), s2))
			result.push_back(i);
	}
	return result;
}

import java.io.*;
import java.util.*;
class Find_Anagram_index
{
public int findIndex(String s1,String s2)
{

char[] c=s1.toCharArray();
Arrays.sort(c);
String s3=new String(c);
//System.out.println(s3);
int len=s3.length();
ArrayList<Character> c2=new ArrayList<Character>();
int index=0;
String result="";


for(int i=0;i<s2.length();i++)
{
c2.clear();


for(int j=0,k=i;j<s3.length();j++,++k)
{
if(k==s2.length())
{
break;
}

char c1=s2.charAt(k);

c2.add(c1);

}

Collections.sort(c2);

StringBuffer s4=new StringBuffer(s3.length());
for (Character c3: c2)
s4.append(c3);
result = s4.toString();

if(s3.equals(result))
{
index=i;
System.out.println(index);

}


}

return index;
}

}

public class Anagram_index
{

public static void main(String args[])
{
Find_Anagram_index f=new Find_Anagram_index();
Scanner s=new Scanner(System.in);
String s1=s.next();
String s2=s.next();

f.findIndex(s1,s2);


}
}

import java.io.*;
import java.util.*;
class Find_Anagram_index

{
public int findIndex(String s1,String s2)
{

char[] c=s1.toCharArray();
Arrays.sort(c);
String s3=new String(c);
//System.out.println(s3);
int len=s3.length();
ArrayList<Character> c2=new ArrayList<Character>();
int index=0;
String result="";


for(int i=0;i<s2.length();i++)
{
c2.clear();


for(int j=0,k=i;j<s3.length();j++,++k)
{
if(k==s2.length())
{
break;
}

char c1=s2.charAt(k);

c2.add(c1);

}

Collections.sort(c2);

StringBuffer s4=new StringBuffer(s3.length());
for (Character c3: c2)
s4.append(c3);
result = s4.toString();

if(s3.equals(result))
{
index=i;
System.out.println(index);

}


}

return index;
}

}

public class Anagram_index
{

public static void main(String args[])
{
Find_Anagram_index f=new Find_Anagram_index();
Scanner s=new Scanner(System.in);
String s1=s.next();
String s2=s.next();

f.findIndex(s1,s2);


}
}

import java.io.*;
import java.util.*;
 class Find_Anagram_index

 {
	public int findIndex(String s1,String s2)
	{
		
		char[] c=s1.toCharArray();
		Arrays.sort(c);
		String s3=new String(c);
		//System.out.println(s3);
		int len=s3.length();
		ArrayList<Character> c2=new ArrayList<Character>();
		int index=0;
		String result="";
		
		
		for(int i=0;i<s2.length();i++)
		{
			c2.clear();
			
			
			for(int j=0,k=i;j<s3.length();j++,++k)
			{
				   if(k==s2.length())
				   {
					   break;
				   }
				 
				   char c1=s2.charAt(k);
				  
				   c2.add(c1);
				  
		    }
			
			Collections.sort(c2);
			
			StringBuffer s4=new StringBuffer(s3.length());
			for (Character c3: c2)
			    s4.append(c3);
		    result = s4.toString();
			
			if(s3.equals(result))
			{
				index=i;
				System.out.println(index);
				
			}
			
			
		}
		
		return index;
	}

}

public class Anagram_index
{
	
	public static void main(String args[])
	{
		Find_Anagram_index f=new Find_Anagram_index();
		Scanner s=new Scanner(System.in);
		String s1=s.next();
		String s2=s.next();
		
		f.findIndex(s1,s2);
		
		
	}
}

A Java approach:

public static void main(String[] args) {
        findIndex("abcd", "abcdefcdbacd");
    }

    private static void findIndex(String s1, String s2) {
        Map<Character, Boolean> map = new HashMap<>();
        for(int i = 0; i < s1.length(); i++)
            map.put(s1.charAt(i), true);
        
        int counter = 0;
        for(int i = 0; i <= s2.length() - s1.length() ; i++){
            if(map.containsKey(s2.charAt(i))){
                map.put(s2.charAt(i), false);
                counter++;
                for(int j = i + 1; j < s1.length() + i; j++){
                    if(map.containsKey(s2.charAt(j))){
                        map.put(s2.charAt(j), false);
                        counter++;
                    }
                    else
                        break;
                }
                if(counter == s1.length())
                    System.out.println(i);
                resetMap(map);
                counter = 0;
            }
        }
    }

    private static void resetMap(Map<Character, Boolean> map) {
        for(Object o : map.entrySet()){
            Map.Entry me = (Map.Entry) o;
            me.setValue(true);
        }
    }

Output: 0, 6, 7, 8. <-- Please notice this should be the correct output in the problem's description