Anagram Substring Search

Question

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.

Answer 1

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.