Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
17
of 17 vote

It is a trick question. First of all, one must realize that solutions like "produce all anagrams..." / search for each in string2 are damn slow, even if we use Boyer-More / Robin Karp and all good stuff. So just forget about this path. Instead, there is a linear solution.

Notice that if any contiguous part of s2 contains contains all characters from s1 and in the same amount, it is an anagram of s1 by definition.

So here is the algo:

Walk s2, 
  while current letter is in s1: count it
  otherwise (letter not in s1): it cannot belong to an anagram,
  so we have what we have ("if solution_found..." - great)
  otherwise start over ("h2 = {}") hoping for the best.

This is algo O(N) (as dictionary operations are O(1))

Python implementation:

import collections # not to build counters by hand

def solution_found(h1, h2):
    return ( all ( (k in h2) for k in h1 )  
             # all letters are present...
             and all (( h2[k] == h1[k] ) for k in h1) 
             # ... and are present in the same amount!
             )

def anagram_is_substring(s1, s2):
    h1 = collections.Counter(s1) # for "abbc", it produces : {"a": 1, "b":2, "c":1}
    h2 = {} # current counters of letters from s1 in s2; 

    for ch in s2:
        if solution_found(h1, h2):
            return True

        if not ch in h1: # this breaks the condition "all letters...", so:
            h2 = {}      # start over
        else:
            if ch not in h2:
                h2[ch] = 0
            h2[ch] += 1

    return False

- Vladislav Kudelin October 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
16
of 32 vote

We check whether there's a substring of b, which has same size and same characters with a.

bool hasAnagramSubstring(const string& src, const string& target)
{
    if(target.size() > src.size()) return false;
    
    int srcLen = src.size(), targetLen = target.size();
    int targetCount[128] = {0}, count[128] = {0}, i, j; 
    //initialize
    for(i = 0; i < target.size(); ++i){
        ++targetCount[target[i]];
        ++count[src[i]];
    }
    //loop
    i = 0;
    while(true){
        //check if substring is an anagram
        for(j = 0; j < targetLen; ++j){
            if(count[target[j]] != targetCount[target[j]]) break;
        }
        if(j == targetLen) return true;
        //slide window
        if(i + 1 + targetLen > srcLen) break;
        --count[src[i]];
        ++count[src[i + targetLen]];
        ++i;
    }
    
    return false;
}

- uuuouou March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Odd that the good solution is just lying there with 0 votes, but a very bad solution gets 3 net upvotes.

- Anonymous March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agreed so why don't you upvote this solution.

- kr.neerav March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anonymous users cannot vote.

- Anonymous March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please explain what slide window does? Thanks.

- Anonymous March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

upvoting this one as you are not trying to find all anagrams and then doing a string match which is an extensive process. Good one :)

- kavitha March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Let me try to explain the sliding window.
We calculate the histogram of string a (length 3). Then we calculate the historgram of the first 3 characters of string b. If it doesn't matches we calculate the histogram of the next set of 3 chars which are at position 1,2,3 and then next 3 which are 2,3,4 etc So it behaves as if we are sliding a windows across the length of string a. Hope it helps.

- kr.neerav March 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

These cases don't work with this solution
("abcdefg", "abcfedgsfdaf")
("a", "cdsgsdgsa")
("abc", "ccccccabbbbbbb")

- kdub454 April 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

targetCount[128] is a nice one.

- axx06xx April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hi, what is the time complexity

- Anonymous April 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

the complexity is O(|src||target|)
take this example
target: aab
src: aadaadaadaadaab

- Anonymous April 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 votes

You can improve this solution. This solution is O(nm), n = lenght of src, m = length of target. We can do this in O(n) time.

In your code above, to check if a substring is an anagram takes O(m).
//check if substring is an anagram
for(j = 0; j < targetLen; ++j){
if(count[target[j]] != targetCount[target[j]]) break;
}

You may do this in O(1) time. Maintain an int variable matchedCount that counts the number of matched characters in current substring(window) and target.

Store target chars in a HashSet to be able to use set.contains() which is O(1).

As you slide the window 1 step to the right, check the following:
1. Decrement matchedCount if the dropped character from the prev window is in target string (use the hashset to query) and if the count of that character after dropping it is now less than its target count.
2.Increment matchedCount if the new character in the new window is in target string (hashset) and if count of that character was less than the targetCount before it was added.

For each iteration (each window), check if matchedCount == target.length() and return true if it is.

Overall time complexity is n * O(1) = O(n)

- j May 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 votes

The suggestion from j is not gone a work.
eg. text ="AAABABAA" and pattern="AAAB"
when the sub string is "BABA", the matchedCount will become 4 and this is wrong.

- Anonymous August 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My solution is here:
public static boolean checkAnagram(String a, String b){
		int lena=a.length();
		int lenb=b.length();
		if(lena>lenb)
			return false;
		if(lena==0||lenb==0){
			return true;
		}
			
		     boolean[] checkTable=new boolean[256];
		     boolean[] tempTable=new boolean[256];
             for(int i=0;i<lena;i++){
                tempTable[a.charAt(i)]=true;
              }
              int count=0;
               checkTable=(boolean[]) tempTable.clone();
		for(int i=0;i<lenb;i++){
		   if(checkTable[b.charAt(i)]==true){
                    count++;
                     if(count==lena)
                        return true;
                  checkTable[b.charAt(i)]=false;
                 }else{
                	checkTable=(boolean[]) tempTable.clone();
                    count=0;
                 }      
		}
		
		return false;
		
	}

- Anonymous February 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

// short and clear

public class Test
{
public static void main(String[] args)
{
Test t=new Test();

System.out.println(t.checkAnagram("afdgzyxksldfm","xyz"));
}

private boolean checkAnagram(String value, String pattern)
{
int [] pat =new int[128];
int j = 0;

for(int i=0;i<pattern.length();i++)
{
pat[pattern.charAt(i)]++;
}

for (int i=0;i<value.length();i++)
{
if(pat[value.charAt(i)]!=0)
{
for(j=1;j<pattern.length();j++)
{
if(pat[value.charAt(i+j)]==0)
break;
}

if(j==pattern.length())
{
return true;
}
}
}

return false;
}

}

- pb November 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 10 vote

My solution:
1- Sort characters of a
2- For each contiguous-character substring S of length == a.Length in b
2.1- Sort the characters of S
2.2- if S == a, return true
3- return false

public bool ContainsAnagram(string a, string b)
{
  if (b.Length < a.Length) return false;

  char[] aArray = a.ToArray<char>();
  Array.Sort(aArray);
  a = new string(aArray);

  for (int i = 0; i <= b.Length - a.Length; i++)
  {
    string sub = b.Substring(i, a.Length);
    char[] subArray = sub.ToArray<char>();
    Array.Sort(subArray);
    sub = new string(subArray);

    if (string.Compare(sub, a, false) == 0) return true;
  }

  return false;
}

- danyluis April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
5
of 5 votes

This solution could be improved this way: instead of sorting each substring (line: "Array.Sort(subArray)") as we move the sliding window through the big string, we can just delete one occurrence of the last character of the substring visited in the previous iteration from the current window's string, and insert-sort the character visited on the current iteration in the current window's string. This small part of the algorithm is only O(M) (M being the length of the anagram string), instead of O(MlogM) which is what it takes to sort it each time. I might publish the code later.

- danyluis April 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Correct me if I am wrong. Considering length of 'a' as m and 'b' as n, time complexity would be O(n*mlogm) for the naive approach and would be O(n*m) for the @danyluis' approach. This can be reduced to Time:O(n) and space:O(m) if we use hashtable

- Yash May 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

Below is a code in Java with O(n) time complexity and O(m) space complexity

public class AnagramSubstring {
	public static void main(String args[]){
		String a="xxyz";
		String b="afyzxydgxzyxksldfm";
		System.out.println(substringAnagram(a,b));
	}
		
	static boolean substringAnagram(String a, String b){
		int[]table=new int[256];
		Arrays.fill(table, 0);
		int[]orig_table=new int[256];
		Arrays.fill(orig_table, 0);
		
		for(int i=0;i<a.length();i++){
			table[a.charAt(i)]++;
			orig_table[a.charAt(i)]++;
		}
		
		int count=0;
		for(int i=0;i<b.length();i++){
			if(table[b.charAt(i)]!=0){
				table[b.charAt(i)]--;
				count++;
				if(count==a.length()){  //match found
					return true;
				}
			}
			else if(count > 0){       //reset
				count=0;
				table=orig_table.clone();
			}

			//else do nothing

		}
		return false;
	}
}

- Yash May 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great! It works just for ASCII though

- Pooyo May 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For Yash's solution, I think it will return true even when all characters from a are present in b but are not contiguous. Doesnt substring mean that all characters should be contiguous?

- cipher May 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about this case
("aaaaaaccccb", "abc");
aaaaaaccccb   // original input
aaaaaabcccc   // sorted input
abc is not a sub string of original input, but is a sub string of sorted input.

- John June 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think Yash's solution time complexity is also O(N*M).
Like the below example(I saw somebody's example).
target: aab
src: aadaadaadaadaab

- xljiasjtu July 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

Here's another solution using a sliding window.

int[] Histogram(string a, int idx, int length)
{
  int buffSize = (int)('z' - 'A' + 1);
  int[] hist = new int[buffSize];
  for (int i = 0; i < length; i++) hist[a[i + idx] - 'A']++;
  return hist;
}

bool SameHist(int[] h1, int[] h2)
{
  for (int i = 0; i < h1.Length; i++)
    if (h1[i] != h2[i]) return false;
  return true;
}

public bool ContainsAnagramSlidingWindow(string a, string str)
{
  if (string.IsNullOrEmpty(a)) return true;
  if (a.Length > str.Length) return false;

  int[] histA = Histogram(a, 0, a.Length); // a's total histogram
  int[] histStr = Histogram(str, 0, a.Length); // str's partial histogram
  int i = 0;
  while (true)
  {
    // Compare str's partial histogram to a's histogram
    if (SameHist(histA, histStr)) return true;
    if (i == str.Length - a.Length) break; 

    // Move window one step ahead
    histStr[str[i] - 'A']--;
    histStr[str[i + a.Length] - 'A']++;
    i++;
  }

  return false;
}

- danyluis April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like the histogram approach. Did you consider using a HashMap so you could compare histograms faster?

- nathan.dudley April 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi: yes! I also thought about doing it with a Dictionary (C#), and I think it would be particularly useful when the alphabet is big. And, also, it wouldn't be more difficult to implement than this solution. Would you be willing to write and post it?

- danyluis April 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

what about this?

Get hash of substring we are searching for (in this case "xyz") and search for that hash using Rabin-Karp or any other rolling hash algorithm. So in this case we would be searching for the hash of "xyz" (which would be the same for any anagram of "xyz") in our string.

- Anonymous March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'd give you more votes if I could to get your answer to top. There are some pretty unreasonable answers at the top right now.

- Orion arm, Laniakea December 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My thought as well. You can generate a hash that evaluates the same across all permutations by mapping each character to a unique prime number. The hash value should be the product of the prime corresponding to each character in the substring.

- Derek July 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

My algorithm
String a;
String b;
get a.length
start traversing b and use substring(i,n)
chk for anagram return true if found else
increment i till i+n<b.length.

code:

import java.util.*;
public class Anachk{	
	public boolean isAnagram(String s,String s1){//a and b in this function will have same length
		char w1[]=s.toCharArray();
		char w2[]=s1.toCharArray();
		if(s.length()!=s1.length())
			return false;
		boolean ch=false;
		HashMap<Character,Integer> chk=new HashMap<Character,Integer>();
		for(int i=0;i<w1.length;i++){
			char c=w1[i];
			if(chk.containsKey(c))
				chk.put(c, chk.get(c)+1);
			else
				chk.put(c, 1);
		}
		for(int i=0;i<w2.length;i++)
		{
			char c=w2[i];
			if(chk.containsKey(c))
				chk.put(c, chk.get(c)-1);
		}
		for(char c:chk.keySet()){
			if(chk.get(c)==0)
				ch=true;
			else{
				ch=false;
				break;
			}
		}
		return ch;
	}
	
	public void func(String a,String b){
		if(0==a.length()||0==b.length()){
			System.out.println("Null strings passed");
			return;
			}
		if(a.length()>b.length()){
			System.out.println("Error check length");
			return;
		}
		int n=a.length();
		int max=b.length();
		int i;
		boolean flag=false;
		String tmp;
		for(i=0;i<max;i++){
			tmp="";
			if(n>max)
				break;
			tmp=b.substring(i,n);
			System.out.print(tmp+"\n");
			flag=isAnagram(a,tmp);
			
			n++;
			if(flag==true)
				break;
		}
		if(flag)
			System.out.println("\nFound at(starting at): "+i+" ends at: "+(n-2));
			else
				System.out.println("Not found");
	}
	
	public static void main(String args[]){
		Anachk z=new Anachk();
		String a="xyz".toLowerCase();
		String b="afdgZyxksldfm".toLowerCase();
		z.func(a, b);
		
	}

}

- _zed April 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

works but why have written your solution multiple times

- l33t April 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is a Java solution with test cases folks.

public class AnagramSubstring {

  public static boolean hasAnagramSubstring(String small, String big) {
    if (small == null || big == null) return false;

    int aLen = small.length(), bLen = big.length();
    if (bLen < aLen) return false;

    byte[] a = new byte[128];
    byte[] b = new byte[128];

    // ASCII code as the index of arrays
    for (int i = 0; i < aLen; i++) a[(int)small.charAt(i)]++;
    for (int i = 0; i < bLen; i++) b[(int)big.charAt(i)]++;

    int j = 0;
    while (j < bLen) {
      // Skip the big-str chars that are not in small-str
      for (; j < bLen && a[(int)big.charAt(j)] == 0; j++);

      // See if we can contiguously match 'aLen' chars in big-str
      int k = 0, z = j;
      while (j < bLen) {
        int c = (int)big.charAt(j);
        if (a[c] == 0) break;
        a[c]--;
        k++; if (k == aLen) return true;
        j++;
      }
      j = z + 1;

      // Since we decr the 'a' array elems above, reinit it for next try
      for (int i = 0; i < aLen; i++) a[(int)small.charAt(i)]++;
    }
    return false;
  }

  public static void main(String[] args) {
    String[] testData = new String[] {
      // small-str    big-str      expected
      null,           null,          "false",
      null,           "",            "false",
      null,           "a",           "false",
      "a",            null,          "false",
      "a",            "",            "false",
      "a",            "a",           "true",
      "ab",           "a",           "false",
      "ab",           "b",           "false",
      "ab",           "ab",          "true",
      "ab",           "ba",          "true",
      "ab",           "aab",         "true",
      "ab",           "abb",         "true",
      "ab",           "zabf",        "true",
      "ab",           "zbaf",        "true",
      "aab",          "zadaabf",     "true",
      "aab",          "zadabaf",     "true",
      "aab",          "zadabaaf",    "true",
      "aabc",         "fbebadabacf", "true",
      "aabc",         "fbebadbadf",  "false",
      "aabc",         "fooabca",     "true"
    };

    for (int j = 0; j < testData.length; j += 3) {
      boolean actual = hasAnagramSubstring(testData[j], testData[j+1]);
      boolean expected = Boolean.parseBoolean(testData[j+2]);
      System.out.printf("|->  %s!.  hasAnagramSubstr('%s', '%s') must be '%s'. "
        + "Got '%s'\n", 
        (actual == expected ? "Pass" : "Fail"),
        testData[j], testData[j+1], expected, actual );
    }
  }
}

And the output:

|->  Pass!.  hasAnagramSubstr('null', 'null') must be 'false'. Got 'false'
|->  Pass!.  hasAnagramSubstr('null', '') must be 'false'. Got 'false'
|->  Pass!.  hasAnagramSubstr('null', 'a') must be 'false'. Got 'false'
|->  Pass!.  hasAnagramSubstr('a', 'null') must be 'false'. Got 'false'
|->  Pass!.  hasAnagramSubstr('a', '') must be 'false'. Got 'false'
|->  Pass!.  hasAnagramSubstr('a', 'a') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('ab', 'a') must be 'false'. Got 'false'
|->  Pass!.  hasAnagramSubstr('ab', 'b') must be 'false'. Got 'false'
|->  Pass!.  hasAnagramSubstr('ab', 'ab') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('ab', 'ba') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('ab', 'aab') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('ab', 'abb') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('ab', 'zabf') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('ab', 'zbaf') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('aab', 'zadaabf') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('aab', 'zadabaf') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('aab', 'zadabaaf') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('aabc', 'fbebadabacf') must be 'true'. Got 'true'
|->  Pass!.  hasAnagramSubstr('aabc', 'fbebadbadf') must be 'false'. Got 'false'
|->  Pass!.  hasAnagramSubstr('aabc', 'fooabca') must be 'true'. Got 'true'

- 1over0 March 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/* 
 * Find if any anagram of a, is present as a substring in b.
 * Returns offset of string b, where anagram can be found.
 * Otherwise: Returns NULL
 */
char * find_anagram(char *a, char *b)
{
    if (!a || !b) return NULL;

    int     i, j;
    int     offset     = 0;
    int     alen       = strlen(a);
    int     blen       = strlen(b);
    char    hash[256]  = {0};

    for (i = 0; i < alen; i++) {
        hash[a[i]]++;
    }

    for (i = 0; i < blen; i++) {
        /* If char available, decrement count,
         * return if this was the last character to match
         */
        if (hash[b[i]] > 0) {
            hash[b[i]]--;
            if (i-offset+1 == alen) {
                return b+offset;
            }
        } else { /* If character not present OR if character exhausted,
                  * then remove the prefix starting from offset, until we
                  * find first character with the same value as current character
                  * i.e. b[i], At that point, move answer(offset) further.
                  * Example: a = "pqrp"; b = "rqpqpptpqprz";
                  */
            for (j=offset; b[j]!=b[i]; j++) {
                hash[b[j]]++;
            }
            offset = j+1;
        }
    }

    return NULL;
}

- mytestaccount2 April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

package com.self.learning.interview.google;

import java.util.regex.Pattern;

public class AnagramTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		// Anagram = forming a new word by rearranging the characters of a word
		// like tail from ital
		
		String s1 = "xyz";
		String s2 = "yzxafdgksldfm";
		
		System.out.println(checkAnagram(s1,s2));

	}
	
	private static boolean checkAnagram(String s1, String s2){
		boolean found = false;
		
		StringBuilder pattern = new StringBuilder();
		
		int len = s1.length();
		
		for(int i=0;i<len;i++){
			pattern.append('[');
			pattern.append(s1);
			pattern.append(']');
		}
		System.out.println("regex : "+pattern);
		Pattern p =  Pattern.compile(pattern.toString());
		
		found = p.matcher(s2).find();
		
		return found;
	}

}

- Ravi April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This one really works

- queen April 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Initialize an array of 26 slots each with the number of times every character appears on string a and then create a copy for such array.

For each character in string b, check if the count on the previously copied array is zero, if so reset the copied array to its original status. Otherwise, decrement the counter and check if all items in the array are now zero, if so, you've found a valid sub-string.

After the for-loop has ended, is safely to assume that no sub-string exists in b.

Time complexity: O(|b|)
Space complexity: O(1)

inline void reset_stats(
    const char origin_stats [],
	const int origin_count,
	char target_stats [],
	int& target_count)
{
	for (int index = 0; index < 26; index++)
		target_stats[index] = origin_stats[index];

	target_count = origin_count;
}

bool is_substr(const string& pattern, const string& search_txt)
{
	if (pattern.length() == 0)
		return true;
	if (pattern.length() > search_txt.length())
		return false;

	int origin_count = pattern.length();

	char origin_stats [26] = { 0 };
	for (int index = 0; index < pattern.length(); index++)
		origin_stats[pattern[index] - 'a']++;

	int current_count;
	char current_stats [26] = { 0 };

	reset_stats(
		origin_stats, origin_count, current_stats, current_count);

	for (int index = 0; index < search_txt.length(); index++)
	{
		if (current_stats[search_txt[index] - 'a'] == 0)
			reset_stats(
				origin_stats, origin_count, current_stats, current_count);
		else
		{
			current_stats[search_txt[index] - 'a']--;
			current_count--;

			if (current_count == 0)
				return true;
		}
	}

	return false;
}

- meh March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Almost correct. However there is a bug in the code. The worst case time complexity is O(NM) where N is length of search string and M is length of pattern string.

Pattern: aabb
Search String : xxbabba
When you are on first 'b' of search string, you start comparing aabb to babba and at last 'b' of search string, you will realize that pattern doesn't match (aabb is not anagram of babb), so instead of simply skipping, we need to compare aabb to abba and return true.
To optimize, this requires to apply KMP algorithm so we can reduce time complexity from O(NM) to O(N)

- Mithya March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code can be fixed as below

for (int index = 0; index < search_txt.length(); index++)
	{
		if (current_stats[search_txt[index] - 'a'] == 0)
			reset_stats(
				origin_stats, origin_count, current_stats, current_count);
		else
		{
                       if(current_stats[search_txt[index] - 'a'] > 0)
                       {      // consider this as a match
			 current_stats[search_txt[index] - 'a']--;
			  current_count--;
                       }
                       else
                       {
                             int cur_index = original_count-current_count;
                             // we matched cur_index characters, 
                             // remove first character from consideration
                            current_stats[search_txt[index-cur_index] - 'a']++;                         
                        }
			if (current_count == 0)
				return true;
		}
	}

- mithya March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mithya
I am not familiar with KMP, but I like what your attempting to do. Resetting the first value that was decremented in the "current_stats" array once you've realized it does not fit in the pattern. Your proposed solution however seems flawed. It appears that the else statement you've added is unreachable. The above code will catch if a value is 0 in the array (and reset), or greater than zero (and decrement it by one). Since no values start at < 0, you will never get to your new code. Also, the current_count variable becomes disjointed with the current_stats array when the increment takes place. This may be by design but if so it's very confusing.

- BenC March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, I realized that. The if part will check for -1 instead. Idea is in array 26, default value should be -1, or a large value e.g. strlen(search_string)+1 because

// Check if the character at all belonged into pattern string
if (current_stats[search_txt[index] - 'a'] == -1 or large value)
{
// Reset and continue
}
else
{

}

- mithya March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Mithya Thanks for your observation!! You're right, I totally missed that case. Please take a look at this other solution I'm proposing that doesn't require KMP and still achieves O(|b|) time complexity with O(1) space:

The idea is to keep an index of the start of the sub-string initially pointing to zero and while reading the search string from left to right check:

a) If the counter in origin_stats for the current character is zero that means that current element is not part of a valid sub-string and it's safe to reset the current stats. Also, start index of sub-string can be changed to index + 1.

b) Else if the counter in current_stats for the current character has become zero, then we need to either regain a character with the same value along the current sub-string and update the start index so that the solution doesn't include it or forfeit the current sub-string if we weren't able to find one.

c) Else just decrement the counter in current_stats and see if we have already found all required characters (this is unchanged from my previous solution).

Cool thing about this is that we're now able to determine the start of the valid sub-string whenever one exists. Here's the code:

inline void reset_stats(
    const char origin_stats [],
    const int origin_count,
	char target_stats [],
	int& target_count)
{
	for (int index = 0; index < 26; index++)
		target_stats[index] = origin_stats[index];

	target_count = origin_count;
}

bool is_substr(const string& pattern, const string& search_txt)
{
	if (pattern.length() == 0)
		return true;
	if (pattern.length() > search_txt.length())
		return false;

	int origin_count = pattern.length();

	char origin_stats [26] = { 0 };
	for (int index = 0; index < pattern.length(); index++)
		origin_stats[pattern[index] - 'a']++;

	int current_count;
	char current_stats [26] = { 0 };

	reset_stats(
		origin_stats, origin_count, current_stats, current_count);

    int substr_start = 0;
	for (int index = 0; index < search_txt.length(); index++)
	{
        if (origin_stats[search_txt[index] - 'a'] == 0)
        {
    		reset_stats(
				origin_stats, origin_count, current_stats, current_count);

            substr_start = index + 1;
        }
		else if (current_stats[search_txt[index] - 'a'] == 0)
        {
            while (search_txt[substr_start] != search_txt[index])
            {
                current_stats[search_txt[substr_start] - 'a']++;
                substr_start++;
                current_count++;
            }

            if (substr_start != index)
                substr_start++;
        }
		else
		{
			current_stats[search_txt[index] - 'a']--;
			current_count--;

			if (current_count == 0)
				return true;
		}
	}

	return false;
}

- meh March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice meh. I would however suggest a quicker reset method. A memcpy would work nice here considering your array is constant size.

Also a quick question for Mithya...
Meh's fix would still run in linear time but as it is now O(2b) it is slightly less optimal. Your original attempt at fixing this did not introduce a second loop. You've modified your if statements to check for negative values to determine if the character exists in the patter, but Meh's solution now has a similar check. I'm wondering if you could post a corrected full implementation to show how this could be done without the use of a second loop (if you still believe it is possible). Thanks

- Anonymous March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

*EDITED*
I don't know much about time complexities and whatnot, but this definitely works!

public class AnagramChecker {

  // Find whether n contains a subset of an anagram of m:
  public Boolean hasAnagram (String n, String m) {
        
    char A[] = n.toCharArray();
    char B[] = m.toCharArray();
    boolean index[] = new boolean [A.length];
    int counter = 0;

    // Search B for an anagram of A, return true if found
    for (int b = 0; b < ( B.length - A.length + 1); b++) { // Loop through B
      for (int d = 0; d < index.length; d++)  // Reset the record
        index[d] = false;
      for (int a = 0; a < A.length; a ++ ) { // Loop through A
        for (int c = b; c < ( b + A.length ); c++) { // Loop through the possible Bs
          if (!index[a]) { // If the A char has not been matched
            if ( A[a] == B[c] ) { // If there is a match,
              index[a] = true; // record the match
              if ( a == (A.length - 1)) { // If it is the last A char to match
                for (int d = 0; d < index.length; d++) { // Check to see if all As matched
                  if (index[d])
                    counter++;
                }
                if ( counter == index.length )
                  return true; // If all matched, return true
                counter=0; // Reset the counter if no match found
              }
            }
          }
        }
      }
    }
        
    // If no anagram found, return false
    return false;
  }

  // Test the function:
  public static void main (String[] args) {
    AnagramChecker AC = new AnagramChecker();
    String first = "supercali";
    String second = "fragilistic";
    String third = "expialidocious";
    String anagram = "dial";
        
    if(AC.hasAnagram(anagram, first))
      System.out.println(first + " contains an anagram of dial");
    else System.out.println(first + " does not contain an anagram of dial");
        
    if(AC.hasAnagram(anagram, second))
      System.out.println(second + " contains an anagram of dial");
    else System.out.println(second + " does not contain an anagram of dial");

    if(AC.hasAnagram(anagram, third))
      System.out.println(third + " contains an anagram of dial");
    else System.out.println(third + " does not contain an anagram of dial");
  }
}

- kloggey March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I just add a main method to run it and put it in my IDE and it works perfectly. (There were a few bugs, but I haven't hand written code in forever!)

public class AnagramChecker {

	// Find whether String b contains a subset of an anagram of String a:
	public Boolean hasAnagram (String n, String m) {

		char A[] = n.toCharArray();
		char B[] = m.toCharArray();

		// Search B for A backwards, return true if found
		for (int b = 0; b < ( B.length - A.length + 1 ); b++) { // Loop through B
			for (int a = ( A.length - 1 ); a >= 0; a -- ) { // Loop through A
				if( B[b] == A[a]) { // Check
					b++; // Check the next cell
					if( a< 1 )
						return true; // If all checks worked, return true
				}
				else { // If a check failed, reset values
					b = b - ((A.length - 1) - a);
					a = 0;
				}
			}
		}

		// If no anagram found, return false
		return false;
	}

	// Test the function:
	public static void main (String[] args) {
	    AnagramChecker AC = new AnagramChecker();
		String first = "supercali";
		String second = "fragilistic";
		String third = "expialidocious";
		String anagram = "ila";
		
		System.out.println("ali is an anagram of ila");
		if(AC.hasAnagram(anagram, first))
			System.out.println(first + " contains the anagram");
		else System.out.println(first + " does not contain the anagram");
		
		if(AC.hasAnagram(anagram, second))
			System.out.println(second + " contains the anagram");
		else System.out.println(second + " does not contain the anagram");

		if(AC.hasAnagram(anagram, third))
			System.out.println(third + " contains the anagram");
		else System.out.println(third + " does not contain the anagram");
	}
}

- kloggey March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

^^^ Anagram doesn't mean "reverse of the word" :)
You maybe need more test cases. Try searching for "abc" inside "zzzzbaczzzz" (should return true)

- S O U N D W A V E March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

That's really funny, I should look these things up!

- kloggey March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;

public class Qs5389078581215232 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        String a = br.readLine();
        String b = br.readLine();

        //Assuming only alphabetic string with lower alphabets
        int[] count = new int[26];

        int lengthB = b.length();
        for (int i = 0; i < lengthB; ++i) {
            char ch = b.charAt(i);
            count[ch-'a']++;
        }

        int lengthA = a.length();
        boolean result = true;
        for (int i = 0; i < lengthA; ++i) {
            char ch = a.charAt(i);
            count[ch-'a']--;
            if (count[ch-'a'] < 0) {
                result = false;
                break;
            }
        }

        out.println(result);
        out.flush();
        out.close();

        System.exit(0);
    }
}

- srikantaggarwal March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Things to note :
1. Difference b/w substring and subsequence
2. Characters can be repeated

<b> The simple approach </b>:

public static boolean hasAnagramSubstring(String a, String b) {
        char[] str = a.toCharArray();
        int seq = -1; 
        int count = 0;
        String subString = "";
        boolean matching = false;
        
        // Traverse through all  char in b
        for (int i = 0; i < b.length(); i++) {      
            if (!matching) {
                seq = i; 
            }
            boolean found = false;
            // For each char in b, search in a
            for (int j = 0; j < str.length; j++) {
                if (b.charAt(i) == str[j] && str[j] != '*') {
                    str[j] = '*'; // If matched, marked it as matched
                    found = matching = true;
                    subString += b.charAt(i);
                    if (++count == a.length()) {
                        System.out.println(subString);
                        return true;
                    }
                    break;
                }
            }
            // Reset
            if (!found && matching) {
                str = a.toCharArray();
                i = seq;
                count = 0;
                matching = false;
                subString = "";
            }
        }
        return false;
    }

- Shubhajit March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

time (n), space o(1)

#include <string>

bool hasPattern(const string &input, const string &pattern) {
  if (input.empty() || pattern.empty() || pattern.size() > input.size()) {
    // error cases
    return false;
  }
  // Uses counting on the alphabet to track anagram.
  char pattern_count[26] = {0};
  for (auto &c : pattern) {
    ++pattern_count[c - 'a'];
  }
  
  // Uses slide window of pattern size to compare whether it could be an anagram
  char input_count[26] = {0};
  // When extra_count equals to zero after initialization, it means it's an
  // anagram.
  int extra_count = 0;
  for (int i = 0; i < pattern.size(); ++i) {
    int index = input[i] - 'a';
    ++input_count[index];
    if (input_count[index] > pattern_count[index]) {
      ++extra_count;
    }
  }
  int i = 0;
  // Moves the slide window.
  while (extra_count > 0 && i < input.size() - pattern.size()) {
    int index = input[i] - 'a';
    if (input_count[index] > pattern_count[index]) {
      --extra_count;
    }
    --input_count[index];
    index = input[i + pattern.size()] - 'a';
    ++input_count[index];
    if (input_count[index] > pattern_count[index]) {
      ++extra_count;
    }
    ++i;
  }
  return extra_count == 0;
}

- Deo March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why didn't somebody write the approach instead lines of code?
Iterate through text.size()-pattern.size()+1 substrings maintaining amount of each character in sliding window pattern.size() size and amount of matched characters. Whenever matched characters equals alphabet size we have found required substring.

- NotImplemented March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this?

Sort the two strings and then find whether the 2nd contains the first as substring.

package com.techsavvykavi;

import java.util.Arrays;

public class Anagram {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String a = "xyz";
		String b = "afdgzyxksldfm";
		boolean match = false;
		char[] pattern = a.toCharArray();
		char[] stringToMatch = b.toCharArray();
		Arrays.sort(pattern);
		Arrays.sort(stringToMatch);
		
		StringBuilder sortedStringToMatch = new StringBuilder();
		sortedStringToMatch.append(stringToMatch);
		if ( sortedStringToMatch.indexOf(new String (pattern) ) == -1 )
			match = false;
		else
			match = true;
		System.out.println( match );

	}

}

- kavitha March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

fails on
xyz
abxcyz

- Darkhan.Imangaliev March 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*using a array of size 26 to represent characters we can easily solve it by traversing base array and checking it against anagram array /*

bool isAnagramOfAIsSubStrOfB(char *str, char *anag, int anag_size)
{
	int arr[26]= {0};
	int i=0, k=0, l = anag_size - 1;
	while(anag[i])
		arr[anag[i++]-97] = 1;
	printf("\nBase String: %s", str);
	printf("\nAnag String: %s", anag);
	i=0;
	while ( str[i] )
	{
		if (arr[str[i] -97] )
		{
			while(arr[str[i] -97])
			{
				arr[str[i] -97] = 0;
				i++;
			}
			k=0;
			l= anag_size - 1;
			while (arr[anag[k] -97] == 0 && l--)
			{
				arr[anag[k]-97] = 1;
				k++;
			}
			if( k == anag_size - 1)
				return true;
			//reset all relevant bits to 1
			k=0;
			while(anag[k])
				arr[anag[k++]-97] = 1;
			i--;
		}
		i++;
	}
	return false;
}

- AgentMac March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool compare(int* countA, int* countB, int num){
	for(int i = 0; i < num; ++i){
		if(countA[i] != countB[i])
			return false;
	}
	return true;
}

bool containsAnagram(string a, string b){
	if(b.length() < a.length())	return false;
	int countA[26];
	int countB[26];
	for(int i = 0; i < a.length(); ++i){
		++countA[a[i] - 'a']; 
	}
	for(int i = 0; i < a.length(); ++i){
		++countB[b[i] - 'a'];
	}
	if(compare(countA, countB, 26))
		return true;
	for(int i = a.length(); i < b.length(); ++i){
		--countB[b[i - a.length()] - 'a'];
		++countB[b[i] - 'a'];
		if(compare(countA, countB, 26))
			return true;
	}
	return false;
}

int main(){
    cout<<(containsAnagram("xyz", "ddzyxmk")?"true":"false")<<endl;
	return 0;
}

- ravio March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool findAnagram (char* a, char* b)
{
int cnts[256] = {0};
char c;
int alen = 0;
while ( a != NULL && *a) {
c = *a;
cnts[c]++;
alen++;
a++;
}
int total_cnt = 0;
while (b != NULL) {
c = *b;
if (--cnts[c] < 0) {
int dt = 0;
do {
cnts[*(b - dt)]++;
dt++;
}
while (dt <= total_cnt);
total_cnt = 0;
}
else
{
if (++total_cnt == alen) {
return true;
}
}
b++;
}
return false;
}

- Anonymous March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in O(m+n), where n is length of a and m is length of b
Suppose a = string whose anagrams are to be found
and b = string to be searched

Algo:
1. search for first occurrence of first character of a in b. If not found return false.
2. Suppose that location is i.
3. Now anagram can be present from i-n-1 to i+n-1 position.
4. Take next character of a and search in range found in step 3.
5. If found repeat step 4 with next character of a until length of a Else repeat step 1 starting at i+n position.
6. If all characters found return true;

- Brinder Pal Singh March 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool HasAnagramSubstring(string data, string sample)
{
int lengD = data.Length;
int lengS = sample.Length;

HashSet<char> map = new HashSet<char>();
foreach (char c in sample)
{
map.add(c);
}

char[] arraySample = sample.ToCharArray();
Array.Sort(arraySample);
string sortedSample = new string(arraySample);

for (int i = 0; i < lengD - lengS; ++i)
{
bool found = true;
// find whether substring starting from i to i + lengS contains all chars
for (int j = i; j < i + lengS; ++j)
{
if (!map.find(data[j])
{
found = false;
i = j;
break;
}
}

if (found)
{
// sort the chars in the string
string temp = data.Substring(i, lengS);
char[] tempArray = temp.ToCharArray();
Array.Sort(tempArray);

// compare the string with sorted sample string
if (sample.EqualsTo(new string(tempArray)))
{
return true;
}
}
}
}

- Anonymous March 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

find longest common subsequence of two strings,if LCS and second string is same will return true,else return false.

- Anonymous March 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Huh? Did you even read the question?

- Anonymous March 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// C#
// O(n + m + m/n = 2m)
public static bool IsAnagram(string a, string b)
{
    if (string.IsNullOrEmpty(a) || string.IsNullOrEmpty(b))
        return false;

    if (a.Length > b.Length)
        return false;

    var dicA = new Dictionary<char, int>();
    // O(n)
    foreach (var ch in a)
    {
        if (dicA.ContainsKey(ch))
            dicA[ch]++;
        else
            dicA.Add(ch, 1);
    }

    var i = 0;
    while (i <= b.Length - a.Length)
    {
        var j = i;
        var dicB = new Dictionary<char, int>();
        // O(m)
        while (j < i + a.Length)
        {
            if (dicB.ContainsKey(b[j]))
            {
                dicB[b[j]]++;
            }
            else
            {
                if (dicA.ContainsKey(b[j]))
                    dicB.Add(b[j], 1);
                else
                    break;
            }
            j++;
        }

        if (j == i + a.Length)
        {
            if (dicA.Count == dicB.Count)
            {
                // O(n), can get into O(m/n) times
                if (dicA.All(kvp => kvp.Value == dicB[kvp.Key]))
                    return true;
            }
            i = j;
        }
        else
        {
            i++;   
        }
    }

    return false;
}

- nemestnyi March 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Implementation of this problem. Time complexit o(m*n)

public static boolean isAnagramExists(String src, String target)
	{
		if (src == null || "".equals(src.trim()) || target == null)
		{
			return false;
		}

		Map<String, Integer> targetCount = new HashMap<String, Integer>();
		Map<String, Integer> srcCount = new HashMap<String, Integer>();
		int targetLen = target.length();
		int srcLen = src.length();
		for (int i = 0; i < target.length(); i++)
		{
			increaseCharCount(target, targetCount, i);

			increaseCharCount(src, srcCount, i);
		}

		int start = 0;

		while (start < srcLen)
		{
			int j = 0;
			for (j = 0; j < targetLen; ++j)
			{
				String targetLetter = String.valueOf(target.charAt(j));

				if (targetCount.get(targetLetter) != srcCount.get(targetLetter))
				{
					break;
				}

			}

			if (j == targetLen)
			{
				return true;
			}

			if (start + 1 + targetLen > srcLen)
				break;

			decreaseCharCount(src, srcCount, start);
			increaseCharCount(src, srcCount, start + targetLen);
			start++;
		}

		return false;
	}

	private static void decreaseCharCount(String string, Map<String, Integer> map, int i)
	{
		String targetLetter = String.valueOf(string.charAt(i));

		if (map.get(targetLetter) == null)
		{
			map.put(targetLetter, 0);
		}
		else
		{
			int count = map.get(targetLetter);
			map.put(targetLetter, --count);
		}
	}

	private static void increaseCharCount(String string, Map<String, Integer> map, int i)
	{
		String targetLetter = String.valueOf(string.charAt(i));

		if (map.get(targetLetter) == null)
		{
			map.put(targetLetter, 1);
		}
		else
		{
			int count = map.get(targetLetter);
			map.put(targetLetter, ++count);
		}
	}

- aviundefined March 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe this is not the optimal solution.. but works....

public static boolean anagram(String s1, String s2) {
		char a2[] = s2.toCharArray();
		Arrays.sort(a2);
		
		String b2 = String.valueOf(a2);
		return (s1.trim().equals( b2.trim() ));
	}
	
	public static boolean search(String str, String stream) {
		int windowLen = str.length();
		int streamLen = stream.length();
		
		char[] a1 = str.toCharArray();
		Arrays.sort(a1);
		String aSorted = String.valueOf(a1);
		
		for( int i = 0; i < streamLen - windowLen; i++ ) {
			String window = stream.substring(i,  i + (windowLen));
			
			if(anagram(aSorted, window) ) {
				return true;
			}
		}
		
		return false;
	}

- Martin March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An On solution as maximum time any character in the larger string is scanned is 2.

import java.io.*;

public class Qs5389078581215232 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        String a = br.readLine();
        String b = br.readLine();

        //Assuming only alphabetic string with lower alphabets
        int[] count = new int[26];
        int lengthA = a.length();
        for (int i = 0; i < lengthA; ++i) {
            char ch = a.charAt(i);
            count[ch-'a']++;
        }

        fill(count, -1);

        int lengthB = b.length();
        int[] temp = copy(count);  
        int start = -1;     
        int matchCount = 0;
        boolean found = false;
        for (int i = 0; i < lengthB; ++i) {
            char ch = b.charAt(i);
            if (temp[ch-'a'] > 0) {
                start = matchCount == 0 ? i : start;
                matchCount++;
                temp[ch-'a']--;
                if (matchCount == lengthA) {
                    found = true;
                    break;
                }
            }    
            else if (temp[ch-'a'] == 0) {
                char tempCh = b.charAt(start);
                while(tempCh != ch) {
                    temp[tempCh-'a']++;
                    matchCount--;
                    start++;
                    tempCh = b.charAt(start);
                }
                start++;    
            }
            else if(temp[ch-'a'] == -1) {
                if (matchCount > 0) {
                    temp = copy(count);
                    matchCount = 0;
                    start = -1;
                }
            }      
        }

        out.println(found);

        out.flush();
        out.close();

        System.exit(0);
    }

    private static int[] copy(int[] A) {
        int lengthA = A.length;
        int[] B = new int[lengthA];

        for (int i = 0; i < lengthA; ++i) {
            B[i] = A[i];
        }
        
        return B;
    }

    private static void fill(int[] A, int num) {
        int lengthA = A.length;
        for (int i = 0; i < lengthA; ++i)
            A[i] = A[i] > 0 ? A[i] : num;
    }
}

- srikantaggarwal March 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple order n solution would be:

1) covert string a into int value. eg if a="ab" then its value is 97+98;
2) now in the string b just iterate till length-2 converting all substrings of length 2 into integer values and compare the results.

- Anonymous March 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but if the string has more than 2 chars, the sum may repeat

- Ana March 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar approach to Rabin-Karp string search algorithm.

// prime number based hash.
#define PRIME 103
uint64_t hash(const char *s, int len)
{
  uint64_t h = 0;
  for (int i = 0; i < len; ++i) {
    h = h*PRIME + s[i];
  }
  return h;
}

int findAnagram(const char *A, const char *B, char *T)
{
  int A_len = strlen(A);
  int B_len = strlen(B);
  if (A_len > B_len) {
    return B_len;
  }

  // PRIME^(A_len-1)
  uint64_t P = 1;
  for (int i = 1; i < A_len; ++i) Hk *= PRIME;

  // get hash value of input string.
  uint64_t H = hash(A, A_len);
  uint64_t h = hash(B, A_len);
  for (int i = 0; i < (B_len - A_len); ++i) {
    if (H == h) {
      strncpy(T, B+i, A_len);
      std::sort(T, T+A_len);
      if (strncmp(A, T, A_len) == 0) {
        return i;
      }
    }
    h = h - B[i] * P + B[i+A_len];
  }
  return B_len;
}

Assume that A is already sorted. When a substring of B shows the same hash value with A, the substring is copied to T and compared one-by-one after being sorted. The time complexity will be O(n + c*m*logm) where n is length of B, m is length of A, and c is the number of false positive cases.

- cjang March 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool IsAnyAnagramASubstring(string a, string b)
{
    var aSorted = Sort(a);
    return SubstringsOfLength(b, a.Length).Any(substring => AreAnagrams(aSorted, substring));
}

// Requires a to be sorted.
private static bool AreAnagrams(string a, string b)
{
    return a.Equals(Sort(b), StringComparison.Ordinal);
}

// Returns all substrings of input of the specified length.
private static IEnumerable<string> SubstringsOfLength(string input, int length)
{
    for (var i = 0; i < input.Length - length; i++)
    {
        yield return input.Substring(i, length);
    }
}

private static string Sort(string input)
{
    var chars = input.ToCharArray();
    Array.Sort(chars);
    return new string(chars);
}

- mattcol March 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterate the string b, if find one char which is contained by a, compare the following a.length() substring of b with a, to see if this substring is anagram of a.
public static boolean isAnagram(String a, String b){
char[] aChars = a.toCharArray();
char[] bChars = b.toCharArray();
Arrays.sort(aChars);
Arrays.sort(bChars);
return String.copyValueOf(aChars).equalsIgnoreCase(String.copyValueOf(bChars));
}
public static void main(String[] args){
String a ="xyd";
String b= "afdgzyxksldfm";
boolean flag = false;
for(int i = 0; i<b.length(); i++){
String s = b.substring(i, i+1);
if(a.contains(s)){
s= b.substring(i, i+a.length());
if(isAnagram(a, s)){
flag = true;
break;
}
}
}
System.out.println("If string a "+a+" is contained by b "+b+" "+flag);
}

- CinderillaLi March 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My algorithm
String a;
String b;
get a.length
start traversing b and use substring(i,n)
chk for anagram return true if found else
increment i till i+n<b.length.

code:

import java.util.*;
public class Anachk{	
	public boolean isAnagram(String s,String s1){//a and b in this function will have same length
		char w1[]=s.toCharArray();
		char w2[]=s1.toCharArray();
		if(s.length()!=s1.length())
			return false;
		boolean ch=false;
		HashMap<Character,Integer> chk=new HashMap<Character,Integer>();
		for(int i=0;i<w1.length;i++){
			char c=w1[i];
			if(chk.containsKey(c))
				chk.put(c, chk.get(c)+1);
			else
				chk.put(c, 1);
		}
		for(int i=0;i<w2.length;i++)
		{
			char c=w2[i];
			if(chk.containsKey(c))
				chk.put(c, chk.get(c)-1);
		}
		for(char c:chk.keySet()){
			if(chk.get(c)==0)
				ch=true;
			else{
				ch=false;
				break;
			}
		}
		return ch;
	}
	
	public void func(String a,String b){
		if(0==a.length()||0==b.length()){
			System.out.println("Null strings passed");
			return;
			}
		if(a.length()>b.length()){
			System.out.println("Error check length");
			return;
		}
		int n=a.length();
		int max=b.length();
		int i;
		boolean flag=false;
		String tmp;
		for(i=0;i<max;i++){
			tmp="";
			if(n>max)
				break;
			tmp=b.substring(i,n);
			System.out.print(tmp+"\n");
			flag=isAnagram(a,tmp);
			
			n++;
			if(flag==true)
				break;
		}
		if(flag)
			System.out.println("\nFound at(starting at): "+i+" ends at: "+(n-2));
			else
				System.out.println("Not found");
	}
	
	public static void main(String args[]){
		Anachk z=new Anachk();
		String a="xyz".toLowerCase();
		String b="afdgZyxksldfm".toLowerCase();
		z.func(a, b);
		
	}

}

- _zed April 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My algorithm
String a;
String b;
get a.length
start traversing b and use substring(i,n)
chk for anagram return true if found else
increment i till i+n<b.length.

code:

import java.util.*;
public class Anachk{	
	public boolean isAnagram(String s,String s1){//a and b in this function will have same length
		char w1[]=s.toCharArray();
		char w2[]=s1.toCharArray();
		if(s.length()!=s1.length())
			return false;
		boolean ch=false;
		HashMap<Character,Integer> chk=new HashMap<Character,Integer>();
		for(int i=0;i<w1.length;i++){
			char c=w1[i];
			if(chk.containsKey(c))
				chk.put(c, chk.get(c)+1);
			else
				chk.put(c, 1);
		}
		for(int i=0;i<w2.length;i++)
		{
			char c=w2[i];
			if(chk.containsKey(c))
				chk.put(c, chk.get(c)-1);
		}
		for(char c:chk.keySet()){
			if(chk.get(c)==0)
				ch=true;
			else{
				ch=false;
				break;
			}
		}
		return ch;
	}
	
	public void func(String a,String b){
		if(0==a.length()||0==b.length()){
			System.out.println("Null strings passed");
			return;
			}
		if(a.length()>b.length()){
			System.out.println("Error check length");
			return;
		}
		int n=a.length();
		int max=b.length();
		int i;
		boolean flag=false;
		String tmp;
		for(i=0;i<max;i++){
			tmp="";
			if(n>max)
				break;
			tmp=b.substring(i,n);
			System.out.print(tmp+"\n");
			flag=isAnagram(a,tmp);
			
			n++;
			if(flag==true)
				break;
		}
		if(flag)
			System.out.println("\nFound at(starting at): "+i+" ends at: "+(n-2));
			else
				System.out.println("Not found");
	}
	
	public static void main(String args[]){
		Anachk z=new Anachk();
		String a="xyz".toLowerCase();
		String b="afdgZyxksldfm".toLowerCase();
		z.func(a, b);
		
	}

}

- _zed April 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My algorithm
String a;
String b;
get a.length
start traversing b and use substring(i,n)
chk for anagram return true if found else
increment i till i+n<b.length.

code:

import java.util.*;
public class Anachk{	
	public boolean isAnagram(String s,String s1){//a and b in this function will have same length
		char w1[]=s.toCharArray();
		char w2[]=s1.toCharArray();
		if(s.length()!=s1.length())
			return false;
		boolean ch=false;
		HashMap<Character,Integer> chk=new HashMap<Character,Integer>();
		for(int i=0;i<w1.length;i++){
			char c=w1[i];
			if(chk.containsKey(c))
				chk.put(c, chk.get(c)+1);
			else
				chk.put(c, 1);
		}
		for(int i=0;i<w2.length;i++)
		{
			char c=w2[i];
			if(chk.containsKey(c))
				chk.put(c, chk.get(c)-1);
		}
		for(char c:chk.keySet()){
			if(chk.get(c)==0)
				ch=true;
			else{
				ch=false;
				break;
			}
		}
		return ch;
	}
	
	public void func(String a,String b){
		if(0==a.length()||0==b.length()){
			System.out.println("Null strings passed");
			return;
			}
		if(a.length()>b.length()){
			System.out.println("Error check length");
			return;
		}
		int n=a.length();
		int max=b.length();
		int i;
		boolean flag=false;
		String tmp;
		for(i=0;i<max;i++){
			tmp="";
			if(n>max)
				break;
			tmp=b.substring(i,n);
			System.out.print(tmp+"\n");
			flag=isAnagram(a,tmp);
			
			n++;
			if(flag==true)
				break;
		}
		if(flag)
			System.out.println("\nFound at(starting at): "+i+" ends at: "+(n-2));
			else
				System.out.println("Not found");
	}
	
	public static void main(String args[]){
		Anachk z=new Anachk();
		String a="xyz".toLowerCase();
		String b="afdgZyxksldfm".toLowerCase();
		z.func(a, b);
		
	}

}

- _zed April 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"""
Given two strings a and b, find whether any
anagram of string a is a sub-string of
string b. For eg:
if a = xyz and b = afdgzyxksldfm then the
program should return true.
"""


def kmp_table(W):
    length = len(W)
    if length == 1:
        return [-1]
    elif length == 2:
        return [-1, 0]
    elif length > 2:
        T = [0] * length
        T[0] = -1
        T[1] = 0
        pos = 2
        cnd = 0
        while pos < length:
            if W[pos - 1] == W[cnd]:
                cnd += 1
                T[pos] = cnd
                pos += 1
            elif cnd > 0:
                cnd = T[cnd]
            else:
                T[pos] = 0
                pos += 1
    return T


def kmp_search(S, W):
    m = 0
    i = 0
    T = kmp_table(W)
    while m + i < len(S):
        if W[i] == S[m + i]:
            if i == len(W) - 1:
                return m
            i += 1
        else:
            m += i - T[i]
            if T[i] > -1:
                i = T[i]
            else:
                i = 0
    return len(S)

- shoudaw April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <map>

using namespace std;

void reset(map<char, pair<int, int> >& contents)
{
  map<char, pair<int, int> >::iterator it;
  for(it = contents.begin(); it != contents.end(); it++)
    it->second.first = it->second.second;
}

bool containsAnagram(string word, string sentence)
{
  map<char, pair<int, int> > contents;
  int i;

  for(i = 0; i < word.size(); i++)
  {
    pair<int, int>& counts = contents[word[i]];
    counts.first = ++counts.second;
  }

  for(i = 0; i < sentence.size(); i++)
  {
    map<char, pair<int, int> >::iterator it = contents.find(sentence[i]);
    while(it != contents.end())
    {
      (it->second.first)--;

      if(i++ + 1 < sentence.size())
        it = contents.find(sentence[i]);
      else
        return false;
    }

    bool foundAnagram = true;
    for(it = contents.begin(); it != contents.end(); it++)
    {
      if(it->second.first != 0)
      {
        foundAnagram = false;
        reset(contents);
        break;
      }
    }

    if(foundAnagram) 
      return true;
  }

  return false;
}

int main()
{
  string word = "xyz";
  string sentence = "11234yxabczyx12";

  if(containsAnagram(word, sentence))
    printf("'%s' contains anagram of '%s'\n", sentence.c_str(), word.c_str());
  else
    printf("'%s' does not contain anagram of '%s'\n", sentence.c_str(), word.c_str());

  return 0;
}

- MAC April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean hasAnagram(String s, String t) {
int[ ] windows = new int[256];
int[ ] record = new int[256];
int count = 0;
for (int i = 0; i < s.length(); i++)
record[s.charAt(i)]++;

for (int i = 0; i < s.length(); i++) {
if (windows[t.charAt(i)] < record[t.charAt(i)]) {
windows[t.charAt(i)]++;
count++;
}
}
if (count == s.length())
return true;

for (int i = 1; i + s.length() - 1 < t.length(); i++) {
char begin = t.charAt(i - 1);
char end = t.charAt(i + s.length() - 1);
if (windows[begin] > 0) {
windows[begin]--;
count--;
}
if (windows[end] < record[end]) {
windows[end]++;
count++;
}
if (count == s.length())
return true;
}
return false;
}

- wxshihe April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findAnagram(sentence,value){
    //validate parameters 
    if(!value || !sentence || value.length > sentence.length)
        return false;
    //create anagram as array
    var anagram = a.split('').reverse();
    
    var match_count = 0;
    for(i = 0;i < sentence.length; i++){
        //if char matches anagram char at the current match index increment counter
        if(sentence[i] == anagram[match_count]){
            match_count++;
            if(match_count == anagram.length){
                //match count matches anagram length, then found return true
                return true;
            }
        }else
           match_count = 0;
    }    
    return false;
}

- Anonymous April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems like a lost war with so many answers but this may be a good solution. From what I think it will work in O(n) time.

public class AnagramUtils {
    public static boolean isAnagramSubString(char[] smallString,char[] bigString){
        if(smallString==null|| bigString==null){
            return false;
        }
        if(smallString.length>bigString.length){
            return false;
        }
        boolean returnVal = false;
        Map <Character,Integer>m = new HashMap<>();
        for(Character c:smallString){
           if(m.containsKey(c)){
               m.put(c,m.get(c)+1);
           } else{
               m.put(c, 1);
           }
        }
        
        Map <Character,Integer>m2 = new HashMap<>();
        for(Character c:bigString){
            if(!m.containsKey(c) && !m2.isEmpty()){
                m2 = new HashMap<>();
            }else if(m.containsKey(c)){
                if(m2.containsKey(c)){
                    m2.put(c, m2.get(c)+1);
                }
                else{
                    m2.put(c, 1);
                }
                if(m.equals(m2)){
                    returnVal = true;
                }
            }else{
                if(!m2.isEmpty()){
                    m2 = new HashMap<>();
                }
            }
        }
       
        return returnVal;
    }

- Anonymous April 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you check this solution for,

smallString = abcd
bigString = bghadabcfgh

- Anonymous April 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAna(String s, String y) {
		StringBuilder sb = new StringBuilder(y);
		y = sb.reverse().toString();
		for(int i =0; i<y.length(); i++) {
			if(y.substring(i).contains(s)) {
				return true;
			}
		}
		return false;
	}

- estfif April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAna(String s, String y) {
		StringBuilder sb = new StringBuilder(y);
		y = sb.reverse().toString();
		for(int i =0; i<y.length(); i++) {
			if(y.substring(i).contains(s)) {
				return true;
			}
		}
		return false;
	}

- estfif April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAna(String s, String y) {
		StringBuilder sb = new StringBuilder(y);
		y = sb.reverse().toString();
		for(int i =0; i<y.length(); i++) {
			if(y.substring(i).contains(s)) {
				return true;
			}
		}
		return false;
	}

- estif April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAna(String s, String y) {
		StringBuilder sb = new StringBuilder(y);
		y = sb.reverse().toString();
		for(int i =0; i<y.length(); i++) {
			if(y.substring(i).contains(s)) {
				return true;
			}
		}
		return false;
	}

- estif April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAna(String s, String y) {
		StringBuilder sb = new StringBuilder(y);
		y = sb.reverse().toString();
		for(int i =0; i<y.length(); i++) {
			if(y.substring(i).contains(s)) {
				return true;
			}
		}
		return false;
	}

- estif April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAna(String s, String y) {
		StringBuilder sb = new StringBuilder(y);
		y = sb.reverse().toString();
		for(int i =0; i<y.length(); i++) {
			if(y.substring(i).contains(s)) {
				return true;
			}
		}
		return false;
	}

- estif April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAna(String s, String y) {
		StringBuilder sb = new StringBuilder(y);
		y = sb.reverse().toString();
		for(int i =0; i<y.length(); i++) {
			if(y.substring(i).contains(s)) {
				return true;
			}
		}
		return false;
	}

- estif April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

aa

- rohit_dayal April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def sub_string(string_a, string_b):
    chars = sorted(string_a)
    for start in range(len(string_b)-len(chars)):
        if chars == sorted(string_b[start:start+len(chars)]):
            return True
    return False

print sub_string("xyz", "afdgzyxksldfm")
print sub_string("xyz", "afdgzyaxksldfm")

- atiurrs April 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assume string a with smaller size and string b with larger size
Logic:
1. find all anagrams of a
2. check if each anagram is a substring of b
3. return true if find one, otherwise return false.

Code:
/*
* find if a string a and all its anagram is a substring of another string b
*/
public static boolean isAnagramsSubstring(String small, String large){
if(small==null||large==null) return false;
if(small.length()>large.length()) return false;
ArrayList<String> anagrams = findAnagrams(small);
for(String s: anagrams){
if(isSubstring(s, large)) return true;
}
return false;
}
private static boolean isSubstring(String a, String b){
for(int i=0; i<b.length(); i++){
if(b.charAt(i)==a.charAt(0)){
if(b.length()-i<a.length()) return false;
String part = b.substring(i, i+a.length());
if(part.equals(a)) return true;
}
}
return false;
}
private static ArrayList<String> findAnagrams(String str){
if(str==null) return null;
return findAnagrams(str, str.length()-1);
}
private static ArrayList<String> findAnagrams(String str, int curIndex){
ArrayList<String> result = new ArrayList<String>();
if(curIndex<0){
result.add("");
return result;
}
ArrayList<String> before = findAnagrams(str, curIndex-1);
for(String s : before){
for(int i=0; i<=s.length(); i++){
String newstr = insert(s, str.charAt(curIndex), i);
result.add(newstr);
}
}
return result;
}
private static String insert(String str, char c, int pos){
String left = str.substring(0,pos);
String right = str.substring(pos);
return left + c + right;
}

- sky April 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Moving window on B; O(b * a) ?

public boolean hasAnagramSubstring(String a, String b){
if(a == null || b == null || a.length() > b.length()){
return false;
}

int[] targetCounts = new int[256];
int[] windowCounts = new int[256];

for(int i = 0; i < a.length(); i++){
targetCounts[a.charAt(i)]++;
windowCounts[b.charAt(i)]++;
}

int length = a.length();

for(int endCursor = a.length() - 1; endCursor < b.length();){
boolean test = isAnagram(targetCounts, windowCounts);
if(test){
return true;
}

windowCounts[b.charAt(endCursor - length + 1)]--;
endCursor++;
if(endCursor >= b.length()){
break;
}else{
windowCounts[b.charAt(endCursor)]++;
}
}

return false;
}

private boolean isAnagram(int[] targetCounts, int[] windowCounts){
for(int i = 0; i < targetCounts.length; i++){
if(targetCounts[i] > 0 && targetCounts[i] != windowCounts[i]){
return false;
}
}

return true;
}

- songofsp3 April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer to this depends whether it's intended to be case sensitive or not, are they alpha numeric only or any character, the size of the character (wide or single byte character), ...etc, but basically, this should work for the basic case of exact matching, and if we wanted we can modify it for any change in the requirement...

bool isContained(char* a, char* b) {
	if (a == NULL || b == NULL){
		return false;
	}

	int CharMap[sizeof(char) << 8];
	ZeroMemory(CharMap, sizeof(CharMap));

	for (char *c = &a[0]; c[0] != '\0'; c++) {
		CharMap[c[0]-1]++;
	}

	for (char *c = &b[0]; c[0] != '\0'; c++) {
		if (CharMap[c[0]-1] > 0) {
			CharMap[c[0]-1]--;
		}
	}

	for (int i = 0; i<_countof(CharMap); i++) {
		if (CharMap[i] != 0) {
			return false;
		}
	}

	return true;
}

- doomdiablos@yahoo.com April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAnagram(String _source1, String _source2)
{

int flag = 0, char_index = 0, counter = 0;
if(_source2.length() < _source1.length()){
return false;
}
char[] _stringchar = _source1.toCharArray();
char[] _tocheck = _source2.toCharArray();
for(char character : _stringchar)
{
char_index = character - 'a';
if((flag & (1 << char_index)) == 0)
flag |= (1 << char_index);
}

for(char toCheckcChar : _tocheck)
{
char_index = toCheckcChar - 'a';

if((flag & (1 << char_index)) > 0)
counter++;
else
counter = 0;

if(counter == _source1.length())
return true;

}

return false;
}

- Roshan May 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAnagram(String _source1, String _source2)
{

int flag = 0, char_index = 0, counter = 0;
if(_source2.length() < _source1.length()){
return false;
}
char[] _stringchar = _source1.toCharArray();
char[] _tocheck = _source2.toCharArray();
for(char character : _stringchar)
{
char_index = character - 'a';
if((flag & (1 << char_index)) == 0)
flag |= (1 << char_index);
}

for(char toCheckcChar : _tocheck)
{
char_index = toCheckcChar - 'a';

if((flag & (1 << char_index)) > 0)
counter++;
else
counter = 0;

if(counter == _source1.length())
return true;

}

return false;
}

- Roshan May 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class Anagram2 {
	private boolean isAnagram(String s, String subStr) {

		HashMap<Character, Integer> map1 = frequnecy(s);
		HashMap<Character, Integer> map2 = frequnecy(subStr);
		for (char c : s.toLowerCase().toCharArray()) {
			if (map2.get(c) == null || map1.get(c) > (map2.get(c))) {

				return false;
			}
		}

		return true;

	}

	private HashMap<Character, Integer> frequnecy(String input) {
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();

		char[] ch = input.toLowerCase().toCharArray();

		for (char c : ch) {
			if (map.containsKey(c)) {

				map.put(c, map.get(c) + 1);

			} else {
				map.put(c, 1);
			}

		}

		return map;

	}

	public static void main(String[] args) {
		Anagram2 testMap = new Anagram2();

		boolean result1 = testMap.isAnagram("xyz", "afdgzxksldfm");
		boolean result2 = testMap.isAnagram("abcdefg", "abcfedgsfdaf");
		boolean result3 = testMap.isAnagram("a", "cdsgsdgsa");
		boolean result4 = testMap.isAnagram("abc", "ccccccabbbbbbb");
		System.out.print(result1);
		System.out.print(result2);
		System.out.print(result3);
		System.out.print(result4);

	}

}

- Mahi July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Anagram2 {
	private boolean isAnagram(String s, String subStr) {
		if(s.length()>subStr.length())
			return false;

		HashMap<Character, Integer> map1 = frequnecy(s);
		HashMap<Character, Integer> map2 = frequnecy(subStr);
		for (char c : s.toLowerCase().toCharArray()) {
			if (map2.get(c) == null || map1.get(c) > (map2.get(c))) {

				return false;
			}
		}

		return true;

	}

	private HashMap<Character, Integer> frequnecy(String input) {
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();

		char[] ch = input.toLowerCase().toCharArray();

		for (char c : ch) {
			if (map.containsKey(c)) {

				map.put(c, map.get(c) + 1);

			} else {
				map.put(c, 1);
			}

		}

		return map;

	}

}

- Mahi July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package google;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class SubStringAnagram {
    @Test
    public void test() {
        assertTrue(hasAnagramAsSubstring("xyz".toCharArray(), "asdnzyxsa".toCharArray()));
        assertFalse(hasAnagramAsSubstring("xyz".toCharArray(), "asdynzxsa".toCharArray()));
    }

    public static boolean hasAnagramAsSubstring(char[] a, char[] s) {
        int[] occ = new int[26];
        Set<Character> anagramLetters = new HashSet<>();

        for (char ac : a) {
            anagramLetters.add(ac);
            occ[ac - 'a']++;
        }

        int[] cur = new int[26];

        for (int i = 0; i < s.length; i++) {
            char curLetter = s[i];
            if (anagramLetters.contains(curLetter)) {
                cur[curLetter - 'a']++;
            }

            if (i >= a.length) {
                char letterToRemove = s[i - a.length];
                if (anagramLetters.contains(letterToRemove)) {
                    cur[letterToRemove - 'a']--;
                }
            }

            if (anagramLetters.contains(curLetter)) {
                boolean found = true;
                for (char l : anagramLetters) {
                    int pos = l - 'a';
                    if (occ[pos] != cur[pos]) {
                        found = false;
                        break;
                    }
                }
                if (found) {
                    return true;
                }
            }
        }
        return false;
    }
}

- Marboni July 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create char array of first variable and sort it and then convert it back to a string.
Now loop through 2nd variable each time picking number of character equal to length of first variable. Sort the picked characters and convert then back to a string and then compare with variable 1. As soon as there is a match break from for loop.

- Rajendra August 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In C++, generate all the permutations of string a and check if they are substrings of b.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool check(string a, string &b){
    sort(a.begin(), a.end());
    do {
        if (b.find(a) != string::npos)
            return true;
    }
    while(next_permutation(a.begin(), a.end()));

    return false;
}

int main(){
    string a, b;
    cin >> a >> b;
    cout << check(a, b);
    return 0;
}

- Inucoder August 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be solved using xor method.

- rishi August 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

algo:
1• Get XOR of current substring
2• XOR result with first few characters of text(few characters=length of substring)
3• Parse text and at each iteration remove last character and add new character till its end or xor==0

- rishi August 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int anagramSubstring(char* text, char* sub)
{
	int sublength=strlen(sub);
	int i=0;
	int xor=0;
	int length=0;
	while(i<sublength)
	{
		xor=xor ^ *(sub+i);
		xor=xor ^ *(text+i);
		i++;
	}   
	
	length=strlen(text);
	while(xor!=0 && i<length)
	{
		xor=xor ^ *(text+i);
		xor=xor ^ *(text+i-sublength);
		i++;
	}

	if(xor==0)
		return 1;
	else 
		return -1;
}

- rishi August 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about this test case:
"aa", "bb"

- madno May 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class whether_any_anagram_of_string_a_is_a_substring_of_string
{
public static void main(String []args)
{
whether_any_anagram_of_string_a_is_a_substring_of_string obj = new whether_any_anagram_of_string_a_is_a_substring_of_string();
String a="xyz";
String b="afdgyzxksldfm";
System.out.println(obj.substringAnagram(a,b));
}

private boolean substringAnagram(String a, String b)
{
boolean table[] = new boolean[256];
boolean orig_table[] = new boolean[256];

Arrays.fill(table,false);
Arrays.fill(orig_table,false);

for(int i=0;i<a.length();i++)
{
table[a.charAt(i)] = true;
orig_table[a.charAt(i)] = true;
}

int count = 0;
for(int j=0;j<b.length();j++)
{
if(table[b.charAt(j)]==true)
{
count++;
table[b.charAt(j)] = false;

if(count==a.length())
{
return true;
}
}

else if(count>0)
{
count = 0;
table = orig_table.clone();
}
}
return false;
}
}

- Prince Seth August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution in Java.

private boolean stringContainsAnagramOfOtherString() {
		
		String a = "xyz";
		String b = "afdgzyxksldfm"; // afdgyzxksldfm
		
		boolean isMapRemoveStarted = false;
		char[] achar = a.toCharArray();
		char[] bchar = b.toCharArray();
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for (int i = 0; i < achar.length; i++) {
			
			int ascii = (int) achar[i];
			map.put(ascii,ascii);
		}
				
		
		for (int i = 0, j = 0; i < bchar.length && j < achar.length ; i++) {
			
			int ascii = (int) bchar[i];
			
			if(map.get(ascii)!=null){
				isMapRemoveStarted = true;
				System.out.println(map.get(ascii)+" ");
				map.remove(ascii);
				j++;
			}else{
				if(isMapRemoveStarted == true)
					j++;
			}
		}
		
		if(map.isEmpty()){
			return true;
		}else{
			return false;
		}
		
	}

- Sanjay Nayak September 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution in Java.

private boolean stringContainsAnagramOfOtherString() {
		
		String a = "xyz";
		String b = "afdgzyxksldfm"; // afdgyzxksldfm
		
		boolean isMapRemoveStarted = false;
		char[] achar = a.toCharArray();
		char[] bchar = b.toCharArray();
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for (int i = 0; i < achar.length; i++) {
			
			int ascii = (int) achar[i];
			map.put(ascii,ascii);
		}
				
		
		for (int i = 0, j = 0; i < bchar.length && j < achar.length ; i++) {
			
			int ascii = (int) bchar[i];
			
			if(map.get(ascii)!=null){
				isMapRemoveStarted = true;
				System.out.println(map.get(ascii)+" ");
				map.remove(ascii);
				j++;
			}else{
				if(isMapRemoveStarted == true)
					j++;
			}
		}
		
		if(map.isEmpty()){
			return true;
		}else{
			return false;
		}
		
	}

- Sanjay Nayak September 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution in Java.

private boolean stringContainsAnagramOfOtherString() {
		
		String a = "xyz";
		String b = "afdgzyxksldfm"; // afdgyzxksldfm
		
		boolean isMapRemoveStarted = false;
		char[] achar = a.toCharArray();
		char[] bchar = b.toCharArray();
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for (int i = 0; i < achar.length; i++) {
			
			int ascii = (int) achar[i];
			map.put(ascii,ascii);
		}
				
		
		for (int i = 0, j = 0; i < bchar.length && j < achar.length ; i++) {
			
			int ascii = (int) bchar[i];
			
			if(map.get(ascii)!=null){
				isMapRemoveStarted = true;
				System.out.println(map.get(ascii)+" ");
				map.remove(ascii);
				j++;
			}else{
				if(isMapRemoveStarted == true)
					j++;
			}
		}
		
		if(map.isEmpty()){
			return true;
		}else{
			return false;
		}
		
	}

- Sanjay Nayak September 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution

private boolean stringContainsAnagramOfOtherString() {
		
		String a = "xyz";
		String b = "afdgzyxksldfm"; // afdgyzxksldfm
		
		boolean isMapRemoveStarted = false;
		char[] achar = a.toCharArray();
		char[] bchar = b.toCharArray();
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for (int i = 0; i < achar.length; i++) {
			
			int ascii = (int) achar[i];
			map.put(ascii,ascii);
		}
				
		
		for (int i = 0, j = 0; i < bchar.length && j < achar.length ; i++) {
			
			int ascii = (int) bchar[i];
			
			if(map.get(ascii)!=null){
				isMapRemoveStarted = true;
				System.out.println(map.get(ascii)+" ");
				map.remove(ascii);
				j++;
			}else{
				if(isMapRemoveStarted == true)
					j++;
			}
		}
		
		if(map.isEmpty()){
			return true;
		}else{
			return false;
		}
		
	}

- Sanjay Nayak September 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
public class CheckAnagram {

	public static void main(String[] args) {
		
		String a = "xyz" ;
		String b = "afdgzylxksldfm";
		checkIfAnagramPresent(a,b);
	}
	
	public static void checkIfAnagramPresent(String a, String b)
	{
		HashMap<Character,Integer> stringMap = new HashMap<Character,Integer>();
		int strlen = a.length();
		for(int i=0;i<a.length();i++)
		{
			
			if(stringMap.containsKey(a.charAt(i)))
			{
				int count = stringMap.get(a.charAt(i));
				stringMap.put(a.charAt(i), count +1);
			}
			else
			{
				stringMap.put(a.charAt(i), 1);
			}
		}
		
		boolean isSubstring = checkForSubstring(stringMap,b,strlen);
		if(isSubstring)
		{
			System.out.println("Substring contains an angram");
		}
		else
			System.out.println("NOt an anagram");
	}
	
	public static boolean checkForSubstring(HashMap<Character,Integer> stringMap, String b, int len)
	{
		int counter =0;
		int j = -1;
		int k = -1;
		for(int i=0;i<b.length();i++)
		{
			
			if(stringMap.containsKey(b.charAt(i)) )
			{
				j =i;
				counter++;
				if(j-k==1)
				{
					if(counter==len)
					{
						return true;
					}
				}
				k =j;
			}
			
		}
		return false;
	}

}

- Anish October 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.BitSet;

public class AnagramSubString {

public static void main(String args[]){
String str = "abcefghi";
String pat = "gefi";

BitSet p = new BitSet(256);
for(int i=0; i<pat.length();i++)
p.set((int)pat.charAt(i));

int np = pat.length();
for(int i=0; i<str.length()-np;i++){
BitSet s = new BitSet(256);
for(int j=0; j<pat.length();j++)
s.set((int)str.charAt(i+j));
if(s.equals(p)){
System.out.println("true");
return;
}
}
System.out.println("false");
}
}

- baps October 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple O(n) code in C++

bool is_anagram_wSubstr(string a, string b)
{
if(a.length() > b.length()) return false;
if(a.length() == 0) return true;

int counter[256];
memset(counter, 0, 256);
for(int i = 0 ; i < a.length(); i++){
counter[(int) a[i]] ++;
counter[(int) b[i]] --;
}

int ind, l = 0, h = a.length() - 1;

while(true){

for(ind = 0 ; ind < a.length() ; ind++)
if(counter[(int) a[ind]] != 0)
break;
if(ind == a.length()) return true;

counter[(int) b[l++]] ++;
if(++h > b.length() - 1) return false;
counter[(int) b[h]] --;
}
}

- SaintMo November 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean anagram(String a, String b){
		if(a.length() > b.length()){
			return false;
		}
		HashMap<Character, Integer> h = new HashMap<Character, Integer>();
		for(int i = 0; i<a.length(); i++){
			if(h.get(a.charAt(i)) == null){
				h.put(a.charAt(i),1);
			}
			else{
				h.put(a.charAt(i),(Integer)h.get(a.charAt(i))+1);
			}
		}
		for(int i = 0; i<b.length(); i++){
			HashMap map = new HashMap<Character,Integer>(h);
			int count = 0,right = i+1;
			if(map.get(b.charAt(i)) != null){
				count++;
				map.put(b.charAt(i),(Integer)map.get(b.charAt(i)-1));
				while(right <b.length()){
					if(count == a.length()){
						return true;
					}
					if(map.get(b.charAt(right)) == null || (Integer)map.get(b.charAt(right)) == 0 ) 
						break;
					else{
						map.put(b.charAt(right),(Integer)map.get(b.charAt(right))-1);					
						right++; count++;
					}
				}
			}
			
		}
	return false;
	} 

     public static void main(String []args){
      	System.out.println(anagram("xyz","axcdefgzyasf"));
     }

- stickypens January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using C++ set

//if any anagram of s1 is a substr of s2
bool anagram(string s1, string s2) {
    set<char> contained;

    for (int i = 0; i< s1.length(); i++) {
        contained.insert(s1[i]);
    }

    for (int j = 0; j < s2.length(); j++) {
        if(contained.find(s2[j]) != contained.end()) {
            contained.erase(s2[j]);
        }

        if (contained.empty()) return true;
    }

    return false;
}

- hoonji April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorting both the strings and using substring is the best way to do it, I guess

- Vpn May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorting both the strings and using substring is the best way to do it, I guess

- Vpn May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Anagram{
public boolean isAnagram(char[] text, char[] sub){
int i = 0;
int k = 0;
int m = sub.length -1;
while(i< sub.length && k < text.length){
if(sub[m-i] == text[k])
i++;
else{
i =0;
}
k++;

if( i == sub.length)
return true;
}

return false;
}

public static void main(String[] args){
String text = "afdgzyxksldfm";
String sub = "xyz";
Anagram ag = new Anagram();
System.out.println("Is Anagram "+ag.isAnagram(text.toCharArray(), sub.toCharArray()));

}
}

- Ebrima Tunkara May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isAnagram(char[] text, char[] sub){
int i = 0;
int k = 0;
int m = sub.length -1;
while(i< sub.length && k < text.length){
if(sub[m-i] == text[k])
i++;
else{
i =0;
}
k++;

if( i == sub.length)
return true;
}

return false;
}

- Ebrima Tunkara May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) time solution and O(M) space given N is the size of B and M is the size of A. Implemented in Groovy with automated tests.

@Unroll
def "isAnagramSubstring(#str1, #str2) == #result"() {
	expect:
	isAnagramSubstring(str1, str2) == result

	where:
	str1			| str2		| result
	"abc"			| "abc"		| true
	"abc"			| "cab"		| true
	"abc"			| "def"		| false
	"abcdefabc"		| "fed"		| true
	"abcdefabc"		| "ghi"		| false
	"abcdeefabc"	| "fed"		| false
	"abcdeefabc"	| "fee"		| true
	"abc"			| ""		| true
	""				| ""		| true
	""				| "def"		| false
}

/*
 abcdadefdabc	| ddef
 5--8
 count | expected
 d: 2	   | 2
 e: 1     | 1
 f: 1     | 1
 charactersCountMatching=2
 */

public boolean isAnagramSubstring(String str1, String str2) {
	if(str1.length() < str2.length()) {
		return false;
	}

	Map<Character, Integer> expectedCount = countCharacters(str2);

	Map<Character, Integer> windowCount = new HashMap<Character, Integer>();
	for(Character c : expectedCount.keySet()) {
		windowCount.put(c, 0);
	}

	int start = 0;
	int end = str2.length() - 1;

	for(int i=0; i <= end; i++) {
		char c = str1.charAt(i);
		if(windowCount.get(c) != null) {
			windowCount.put(c, windowCount.get(c)+1);
		}
	}

	int charactersCountMatching = 0;
	for(Character c : windowCount.keySet()) {
		if(windowCount.get(c) == expectedCount.get(c)) {
			charactersCountMatching++;
		}
	}

	if(charactersCountMatching == expectedCount.size()) {
		return true;
	}

	while(end+1 < str1.length()) {
		start++;
		end++;

		char removedChar = str1.charAt(start-1);
		if(windowCount.get(removedChar) != null) {
			if(windowCount.get(removedChar) == expectedCount.get(removedChar)) {
				charactersCountMatching--;
			}

			windowCount.put(removedChar, windowCount.get(removedChar)-1);
			if(windowCount.get(removedChar) == expectedCount.get(removedChar)) {
				charactersCountMatching++;
			}
		}

		char addedChar = str1.charAt(end); //d
		if(windowCount.get(addedChar) != null) {
			if(windowCount.get(addedChar) == expectedCount.get(addedChar)) {
				charactersCountMatching--;
			}

			windowCount.put(addedChar, windowCount.get(addedChar)+1);
			if(windowCount.get(addedChar) == expectedCount.get(addedChar)) {
				charactersCountMatching++;
			}
		}

		if(charactersCountMatching == windowCount.size()) {
			return true;
		}

	}

	return false;
}

private Map<Character, Integer> countCharacters(String str) {
	Map<Character, Integer> result = new HashMap<Character, Integer>();

	for(int i = 0; i < str.length(); i++) {
		char c = str.charAt(i);
		if(result.get(c) == null) {
			result.put(c, 0);
		}

		result.put(c, result.get(c)+1);
	}

	return result;
}

- carlosgsouza June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool function(string src, string dst)
{
    bool hash[26] = {false};
    for(int i=0;i<src.length();i++)
        hash[(int)src[i]-97] = true;
    int count = src.length();
    for(int i=0;i<dst.length();i++)
    {
        if(!count)
            return true;
        if(hash[(int)dst[i]-97])
        {
            count--;
            continue;
        }
        else
            count = src.length();
    }
    return false;
}

- skum July 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean anagramString(String str1, String str2) {
if (str1 == null || str2 == null) return false;
if(str1.length() == 0 || str2.length() == 0) {
return false;
}
if(str1.equals(str2)) return true;

while(true) {
char ch = str1.charAt(0);
int len2 = str2.length();
int index2 = str2.indexOf(ch);
str1 = str1.substring(1);
if (index2 == -1) return false;
str2 = str2.substring(0, index2).concat(str2.substring(index2+1, len2));
if(str1.length() == 0 && str2.length() == 0) return true;

}
}

- Sudhakar August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{public static boolean anagramString(String str1, String str2) {
if (str1 == null || str2 == null) return false;
if(str1.length() == 0 || str2.length() == 0) {
return false;
}
if(str1.equals(str2)) return true;

while(true) {
char ch = str1.charAt(0);
int len2 = str2.length();
int index2 = str2.indexOf(ch);
str1 = str1.substring(1);
if (index2 == -1) return false;
str2 = str2.substring(0, index2).concat(str2.substring(index2+1, len2));
if(str1.length() == 0 && str2.length() == 0) return true;

}
}}

- Sudhakar August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean findIfAna(String a, String b){
		int length = 0;
		HashMap<Character,Integer> aHash = new HashMap<Character,Integer>();
		List<Character> aList = new LinkedList<Character>();
		for(int i =0;i<a.length();i++)
			aHash.put(a.charAt(i),(int) a.charAt(i));
		for(int i = 0;i<b.length();i++){
			char cur = b.charAt(i);
			if(aHash.containsKey(cur)){
				aList.add(cur);
				aHash.remove(cur);
				length++;
				if(length==a.length())
					return true;
			}
			else if(aList.size()!=0){
				char temp = aList.remove(0);
				if(temp==cur)
					aList.add(cur);
				else{
					aHash.put(temp,(int)temp);
					length--;
				}
			}
		}
		return false;

}

- Davidk June 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My implementation is Python. There's a bit code repetition and I have some doubts about the efficiency. but it works

import re


def right_match(a,b):
    """ checks if any character of a is in b right edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:
        index = a.index(b[-1])
    except:
        return False;
    return right_match(a[:index]+a[index+1:],b[0:-1])

def left_match(a,b):
    """ checks if any character of a is in b left edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:                       
        index = a.index(b[0])
    except:
        return False
    return left_match(a[:index]+a[index+1:],b[1:0])
    
def special_contains(a,b):
    """ finds if anagram of a contains in b """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    
    # step one - find all occurances of a[0]
    # assuming a is alphanumeric character
    occurances = [m.start() for m in re.finditer(a[0:1],b)]
    # if that wasn't found then false for sure
    if len(occurances) == 0 : return False 
    for index in occurances:
        for i in range(len(a)):
            if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
    return False

- Or Shachar September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my implementation in Python. There's a bit code repetition and I have some doubts about the efficiency but it works.

import re


def right_match(a,b):
    """ checks if any character of a is in b right edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:
        index = a.index(b[-1])
    except:
        return False;
    return right_match(a[:index]+a[index+1:],b[0:-1])

def left_match(a,b):
    """ checks if any character of a is in b left edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:                       
        index = a.index(b[0])
    except:
        return False
    return left_match(a[:index]+a[index+1:],b[1:0])
    
def special_contains(a,b):
    """ finds if anagram of a contains in b """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    
    # step one - find all occurances of a[0]
    # assuming a is alphanumeric character
    occurances = [m.start() for m in re.finditer(a[0:1],b)]
    # if that wasn't found then false for sure
    if len(occurances) == 0 : return False 
    for index in occurances:
        for i in range(len(a)):
            if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
    return False

- Or Shachar September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my implementation in Python. There's a bit code repetition and I have some doubts about the efficiency but it works.

import re

def right_match(a,b):
    """ checks if any character of a is in b right edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:
        index = a.index(b[-1])
    except:
        return False;
    return right_match(a[:index]+a[index+1:],b[0:-1])

def left_match(a,b):
    """ checks if any character of a is in b left edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:                       
        index = a.index(b[0])
    except:
        return False
    return left_match(a[:index]+a[index+1:],b[1:0])
    
def special_contains(a,b):
    """ finds if anagram of a contains in b """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    
    # step one - find all occurances of a[0]
    # assuming a is alphanumeric character
    occurances = [m.start() for m in re.finditer(a[0:1],b)]
    # if that wasn't found then false for sure
    if len(occurances) == 0 : return False 
    for index in occurances:
        for i in range(len(a)):
            if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
    return False

- Or Shachar September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check

- Or d September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import re


def right_match(a,b):
    """ checks if any character of a is in b right edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:
        index = a.index(b[-1])
    except:
        return False;
    return right_match(a[:index]+a[index+1:],b[0:-1])

def left_match(a,b):
    """ checks if any character of a is in b left edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:                       
        index = a.index(b[0])
    except:
        return False
    return left_match(a[:index]+a[index+1:],b[1:0])
    
def special_contains(a,b):
    """ finds if anagram of a contains in b """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    
    # step one - find all occurances of a[0]
    # assuming a is alphanumeric character
    occurances = [m.start() for m in re.finditer(a[0:1],b)]
    # if that wasn't found then false for sure
    if len(occurances) == 0 : return False 
    for index in occurances:
        for i in range(len(a)):
            if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
    return False

- Shachar September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import re


def right_match(a,b):
""" checks if any character of a is in b right edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[-1])
except:
return False;
return right_match(a[:index]+a[index+1:],b[0:-1])

def left_match(a,b):
""" checks if any character of a is in b left edge """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False
try:
index = a.index(b[0])
except:
return False
return left_match(a[:index]+a[index+1:],b[1:0])

def has_anagram_substring(a,b):
""" finds if anagram of a contains in b """
# True in empty way
if len(a) == 0 : return True
# can never be true
if len(a) > len(b) : return False

# step one - find all occurances of a[0]
# assuming a is alphanumeric character
occurances = [m.start() for m in re.finditer(a[0:1],b)]
# if that wasn't found then false for sure
if len(occurances) == 0 : return False
for index in occurances:
for i in range(len(a)):
if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
return False

- Or Shachar September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Heres my implementation in python. a bit code repetition but it works:

import re


def right_match(a,b):
    """ checks if any character of a is in b right edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:
        index = a.index(b[-1])
    except:
        return False;
    return right_match(a[:index]+a[index+1:],b[0:-1])

def left_match(a,b):
    """ checks if any character of a is in b left edge """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    try:                       
        index = a.index(b[0])
    except:
        return False
    return left_match(a[:index]+a[index+1:],b[1:0])
    
def has_anagram_substring(a,b):
    """ finds if anagram of a contains in b """
    # True in empty way
    if len(a) == 0 : return True
    # can never be true
    if len(a) > len(b) : return False
    
    # step one - find all occurances of a[0]
    # assuming a is alphanumeric character
    occurances = [m.start() for m in re.finditer(a[0:1],b)]
    # if that wasn't found then false for sure
    if len(occurances) == 0 : return False 
    for index in occurances:
        for i in range(len(a)):
            if right_match(a[1:1+i],b[:index]) and left_match(a[1+i:],b[index+1:]) : return True
    return False

- Or Shachar September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved by using  Robin Karp String matching algorithm. Use hash function to evaluate value of String "a" and apply Robin karp search algorithm on String B and check for hash value.

- Amit Kumar November 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use this method in python as it does not have limit on int..

for a to z assign one prime number to each so there will be first 26 prime numbers assigned..now for string a do multiplication of prime number assigned to each character and now for that substring length try to do same in string b....if mul matches then return true

- kishanvadalia.vadalia January 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import re
sub = input('enter a substring (anagram): ')
pattern1 = r'('+sub+')'
pattern2 = r'('+sub[::-1]+')'
s = input('enter a string: ')
l = re.findall(pattern1,s)
ll = re.findall(pattern2,s)
print([i for i in l]+[j for j in ll])

- Saidu D March 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This algorithm consists of:
(1) checking the least frequent element of a in b
(2) find all the occurrences of this in b
(3) from each position look left and right to see if there are other contiguous characters from a

def decrement_counter(counter, key):
    counter[key] -= 1
    if counter[key] == 0:
        del counter[key]

    return counter


def contains_anagram(a, b):
    if len(b) < len(a):
        return False
    
    a_counter, b_counter = Counter(a), Counter(b)
    less_freq_char = min(a, key=lambda x: b_counter[x])
    decrement_counter(a_counter, less_freq_char)

    queue = deque()
    for k, c in enumerate(b):
        if c == less_freq_char:
            queue.appendleft([k, k+1, a_counter])

    while queue:
        start, end, prev_counter = queue.pop()
        num_elms = sum(prev_counter.values())

        if start > 1 and b[start-1] in prev_counter:
            if num_elms == 1:
                return True

            new_counter = decrement_counter(Counter(prev_counter), b[start-1])
            queue.appendleft([start-1, end, new_counter])

        if end < len(b) and b[end] in prev_counter:
            if num_elms == 1:
                return True
            
            new_counter = decrement_counter(Counter(prev_counter), b[end])
            queue.appendleft([start, end+1, new_counter])

    return False

- Flint October 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a single-liner in python that runs in O(nlogn) time:

import re
def f(a,b):
    return re.fullmatch('.*'+'.*'.join(sorted(a))+'.*',''.join(sorted(b)))

It could be made faster by using radix sort instead of using the built-in "sorted" function, which is a variation of merge-sort

- Anonymous November 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time O(n), Space O(n)
1. Put every char of anagram in hash data structure
2. Iterate through string.
a. If current char is in hash,
a1.Remove the char from hash. If hash is empty(), return true
b. If not, reset hash, repeat a1.

- Nima December 21, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 13 vote

Will this one work...

Search for the occurrence of any character of string a in string b. Let this character be x.

If found, generate all anagrams of string a starting with x and check whether the same pattern is found in string b.

If found return true, else continue finding the next character

- arsragavan March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not sure if I am getting your solution right, the time complexity is O(k!n) right ?
where k = len(string a)
and n = len(string b)

- krbchd March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution doesn't handle sol for below mentioned scenario:

String 1:
abc

String 2:
xncbabkl

As per ur sol:
i picked any char from string 1 lets say 'a'
and then found all the anagrams starting with 'a':

abc
acb

but both of the anagrams are not present in string 2
Your sol is missing checking 'cba' case.

- PKT March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

No, my solution asks to look for any character of string a in string b..

From your example: characters in string a = {a,b,c}
While traversing string b, it detects character c and then generate two possible combinations - cab, cba and check whether the combinations are present in string b which will be found. So, will return true..

We can maintain the characters of string a in a hashmap so that search will take just O(1) time for each of the characters of string b.

- arsragavan March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

oh ok....
you comment "any character of string a" made to think of this corner case which can be handled easily as you mentioned.
nice sol.

- PKT March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

simply store all characters of string b in hashtable.

Check whether all characters of string a is present in or not?

- Coder March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

// 1. get all anagram strings of a
// 2. for each string in the anagram list, check if it is a substring of b

bool AnagramIsSubString(string a, string b)
{
string[] anagrams = GetAllAnagram(a);
bool found = false;

foreach (string anagram in anagrams)
{
if (b.IndexOf(anagram) != -1)
{
found = true;
break;
}
}
return found;
}

- vincenth March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

finding all anagram is expensive. use the other approach. Here is the c# code.

static bool AnagramIsSubstring(string a, string b)
{
if (a == null || b == null || a.Length > b.Length)
{
return false;
}

char[] achars = a.ToCharArray();
Array.Sort(achars);
string sorteda = new string(achars);

HashSet<char> aset = new HashSet<char>();
foreach (char c in achars)
{
aset.Add(c);
}

for (int i = 0; i < b.Length - a.Length + 1; ++i)
{
bool found = true;
for (int j = i; j < i + a.Length; ++j)
{
if (!aset.Contains(b[j]))
{
found = false;
break;
}
}

if (found)
{
char[] bchars = b.Substring(i, a.Length).ToCharArray();
Array.Sort(bchars);
string sortedb = new string(bchars);

if (string.Compare(sortedb, sorteda) == 0)
{
return true;
}
}
}

return false;
}

- Anonymous March 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Using the xor function

- Anonymous March 26, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More