6
\$\begingroup\$

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.
\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.