Determining the existence of string Intersections

Question

Problem:

Given 2 strings, consider all the substrings within them of length len. Len will be 1 or more. Returns true if there are any such substrings which appear in both strings. Compute this in linear time using a HashSet.

Solution:

import java.util.HashSet;

public class Standford3 {
    public static void main(String[] args) {
        System.out.println("Test 1: " +
            (false  == stringIntersect("blahblah", "foralheh", 3))
        );
        System.out.println("Test 2: " +
            (true  == stringIntersect("checking", "deck", 2))
        );
        System.out.println("Test 3: " +
            (false  == stringIntersect("derping", "slurp", 3))
        );
        System.out.println("Test 4: " +
            (false  == stringIntersect("foo", "bar", 1))
        );
        System.out.println("Test 5: " +
            (true  == stringIntersect("nowai", "55&dcsnow", 3))
        );
    }

    public static boolean stringIntersect(String a, String b, int len) {
        if (a.length() == 0 || b.length() == 0) { return false; }

        HashSet<String> alpha = permutateString(a, len);
        HashSet<String> beta = permutateString(b, len);

        for (String s : alpha) {
            if (beta.contains(s)) { return true; }
        }

        return false;
    }


    public static HashSet<String> permutateString(String str, int i) {
        if (i > str.length()) {
            throw new IllegalArgumentException(
                "Substring length cannot be larger than provided string"
            );
        }

        HashSet<String> set = new HashSet<>();
        int count = i;

        for (int j = 0; j < str.length(); j++ ) {
            if (count > str.length()) { break; }

            set.add(str.substring(j, count));
            count++;
        }

        return set;
    }
}

1. Are these tests sufficient? Unlike the two challenges that preceded it, the tests are mine; is there anything I should be testing for that I missed?

2. I hope this isn't outside of codereview territory, but I'm wondering if something more was meant by "compute in linear time" or does this adequately encompass that requirement?

3. Although the use of HashSet was explicitly cited, I'm wondering if there are performance advantages in using another built in class like LinkedHashSet?

Answer 1

Some simple suggestions for refactoring on your current code (without going into the implementation)

1. Use Set over HashSet

Your original question says "Compute this in linear time using a HashSet.", but that usually doesn't mean you need to use HashSet as the return type. Set<String> result = new HashSet<>() works better in the sense that callers of your method will not need to know the underlying implementation. Also, you'll be free to change it to LinkedHashSet without changing the method signature.

2. Variable names

Two points here.

i is usually used in for loops, so do consider using a better name in the method signature, e.g. permutateString(String str, int length).

Your count isn't actually counting anything, but to keep track of the last exclusive index for substring-ing (I think I just made a new word up!). For people who don't use String.substring() often, that line of code will instead read like you are creating sub-strings of increasing lengths.

3. Looping

   for (int j = 0; j < str.length(); j++ ) {
       if (count > str.length()) { break; }
       ...
   }
   

   This can be better expressed as:

   for (int j = 0; j <= str.length() - length; j++ ) {
       result.add(str.substring(j, j + length));
   }
   

   Illustration:

   1234567890
   123
    234
     345
      456
       567
        678
         789
          890
   

   So, to extract 3-character sub-strings from a 10-character string, we need to loop from i = 0 to i = 7, or i <= string.length() - length for the latter.

4. Unit testing

As mentioned elsewhere, please consider using unit testing frameworks like JUnit or TestNG. :)