## Google Interview Question for Software Engineer / Developers

• 19

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``````

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;
}``````

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.

Comment hidden because of low score. Click to expand.
0

Agreed so why don't you upvote this solution.

Comment hidden because of low score. Click to expand.
0

Anonymous users cannot vote.

Comment hidden because of low score. Click to expand.
0

can you please explain what slide window does? Thanks.

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 :)

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.

Comment hidden because of low score. Click to expand.
-2

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

Comment hidden because of low score. Click to expand.
0

targetCount[128] is a nice one.

Comment hidden because of low score. Click to expand.
0

hi, what is the time complexity

Comment hidden because of low score. Click to expand.
2

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

Comment hidden because of low score. Click to expand.
5

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)

Comment hidden because of low score. Click to expand.
-1

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.

Comment hidden because of low score. Click to expand.
0

``````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;

}``````

Comment hidden because of low score. Click to expand.
0

// 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;
}

}

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;
}``````

Comment hidden because of low score. Click to expand.
5

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.

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

Comment hidden because of low score. Click to expand.
3

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;
}
}``````

Comment hidden because of low score. Click to expand.
0

Great! It works just for ASCII though

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

``````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.``````

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

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

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

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
}

public static void main(String args[]){
Anachk z=new Anachk();
String a="xyz".toLowerCase();
String b="afdgZyxksldfm".toLowerCase();
z.func(a, b);

}

}``````

Comment hidden because of low score. Click to expand.
0

works but why have written your solution multiple times

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",
"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', 'fooabca') must be 'true'. Got 'true'``````

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;
}``````

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;
}

}``````

Comment hidden because of low score. Click to expand.
0

This one really works

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;
}``````

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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;
}
}``````

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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
{

}

Comment hidden because of low score. Click to expand.
0

@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;
}``````

Comment hidden because of low score. Click to expand.
0

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

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");
}
}``````

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");
}
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
3

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

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 {
PrintWriter out = new PrintWriter(System.out);

//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);
}
}``````

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;
}``````

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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

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

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 );

}

}``````

Comment hidden because of low score. Click to expand.
0

``````fails on
xyz
abxcyz``````

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;
}``````

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;
}``````

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;
}

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;

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)
{
}

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;
}
}
}
}

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.

Comment hidden because of low score. Click to expand.
0

Huh? Did you even read the question?

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
}

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]))
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;
}``````

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);
}
}``````

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;
}``````

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 {
PrintWriter out = new PrintWriter(System.out);

//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;
}
}``````

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.

Comment hidden because of low score. Click to expand.
0

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

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.

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);
}``````

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);
}

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
}

public static void main(String args[]){
Anachk z=new Anachk();
String a="xyz".toLowerCase();
String b="afdgZyxksldfm".toLowerCase();
z.func(a, b);

}

}``````

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
}

public static void main(String args[]){
Anachk z=new Anachk();
String a="xyz".toLowerCase();
String b="afdgZyxksldfm".toLowerCase();
z.func(a, b);

}

}``````

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
}

public static void main(String args[]){
Anachk z=new Anachk();
String a="xyz".toLowerCase();
String b="afdgZyxksldfm".toLowerCase();
z.func(a, b);

}

}``````

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)``````

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;
}``````

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;
}

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;
}``````

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;
}``````

Comment hidden because of low score. Click to expand.
0

can you check this solution for,

smallString = abcd

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;
}``````

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;
}``````

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;
}``````

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;
}``````

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;
}``````

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;
}``````

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;
}``````

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

aa

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")``````

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){
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);
}
}
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;
}

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;
}

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;
}``````

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;
}

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;
}

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);

}

}``````

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;

}

}``````

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) {
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;
}
}``````

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.

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;
}``````

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

It can be solved using xor method.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

"aa", "bb"

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;
}
}

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;
}

}``````

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;
}

}``````

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;
}

}``````

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;
}

}``````

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;
}

}``````

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");
}
}

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]] --;
}
}

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"));
}``````

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;
}``````

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

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

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()));

}
}

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;
}

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
}

/*
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++;
}
}

charactersCountMatching--;
}

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;
}``````

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;
}``````

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;

}
}

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;

}
}}

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>();
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)){
aHash.remove(cur);
length++;
if(length==a.length())
return true;
}
else if(aList.size()!=0){
char temp = aList.remove(0);
if(temp==cur)
else{
aHash.put(temp,(int)temp);
length--;
}
}
}
return false;``````

}

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``````

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``````

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``````

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

check

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``````

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

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``````

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.``

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

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])``````

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``````

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

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.

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

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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.

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.

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.

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?

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;
}

Comment hidden because of low score. Click to expand.
0

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)
{
}

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;
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Using the xor function

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.

### 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.