# Anagram Substring Search

I am having difficulty understanding the runtime and space complexity while implementing the said question.

Following is the code:

import java.util.HashMap;
import java.util.Map;

public class AnagaramInBigString {

private static Map<Character, Integer> frequencyMap(String str)
{
Map<Character, Integer> source = new HashMap<Character,Integer>();
for(int i = 0; i < str.length(); i++)
{

if(str.charAt(i) == ' ')
{
continue;
}
else
{

if(source.containsKey(str.charAt(i)))

{
source.put(str.charAt(i), source.get(str.charAt(i) + 1));
}
else source.put(str.charAt(i), 1);
}
}

return source;
}

public static void main(String []args)
{
String check= "BACDGABCDA";
String sample = "ABCD";
System.out.println(sample.length());

for(int i= 0; i <= check.length() - sample.length() ; i++)
{
String checkSub = check.substring(i, i + sample.length());
System.out.println(checkSub);
System.out.println(frequencyMap(checkSub).equals(frequencyMap(sample)));
}
}

}


Is the time complexity O(check*sample)? Space complexity is O(sample)? Also please suggest on how I can improve the efficiency of this code.

Like:

1. I can calculate the hashmap for sample string only once instead of doing it again and again with every iteration.

Time and space complexity is usually represented with n and m, so O(check*sample) and O(sample) would be O(nm) and O(n).

For complexity, if m is sample, and n is check, time complexity is actually O(n(n-m)), or $O(n^2 - m)$, which I would say is simple O(n). Same with space complexity, as well (this I am not sure about, please correct me if I am incorrect).

Also, you have:

public class AnagaramInBigString {


and:

private static Map<Character, Integer> frequencyMap(String str)
{


One word to describe this: inconsistency. Be consistent. Either have a newline, or don't.

I suggest not have a new line, as it wastes newlines, and doesn't it make it a bit more readable. It also follows Java conventions.

This crazy code:

    if(str.charAt(i) == ' ')
{
continue;
}
else
{

if(source.containsKey(str.charAt(i)))

{
source.put(str.charAt(i), source.get(str.charAt(i) + 1));
}
else source.put(str.charAt(i), 1);
}


I can't even follow it. In addition to the above suggestion, always put braces for if, for, and while statements, no matter how long or short the statements are. Result:

    if (str.charAt(i) == ' ') {
continue;
} else {
if (source.containsKey(str.charAt(i))) {
source.put(str.charAt(i), source.get(str.charAt(i) + 1));
} else {
source.put(str.charAt(i), 1);
}
}


The continue can be removed by reversing the expression:

    if (str.charAt(i) != ' ') {
if (source.containsKey(str.charAt(i))) {
source.put(str.charAt(i), source.get(str.charAt(i) + 1));
} else {
source.put(str.charAt(i), 1);
}
}


and the put can be simplified with ternary:

    if (str.charAt(i) != ' ') {
source.put(str.charAt(i), source.containsKey(str.charAt(i)) ?
source.get(str.charAt(i) + 1) :
1);
}


Also consider using JUnit 4 for testing.

• Thanks for the suggestions. Is the time and space complexity correct? – Himanshu Verma Dec 17 '15 at 0:35
• Well, not exactly. Take a look at edit, coming shortly. – TheCoffeeCup Dec 17 '15 at 0:35
• Shouldn't space complexity be O(m) considering m is the size of "Sample" as I am only creating hash map of m size. – Himanshu Verma Dec 17 '15 at 1:45
• @HimanshuVerma Except you are creating it n-m times. – TheCoffeeCup Dec 17 '15 at 1:51
• Yes. I think I need to look into how to calculate space-time complexity. I am having difficulties in calculating. – Himanshu Verma Dec 17 '15 at 14:58