Find if string contains the substring without Java.substring

Finding the longest common substring first will be slower than just checking whether there is a match of at least a given size. You can stop as soon as you get a match, even if there could have been a longer one.

I would build a hash set (or a hash map if the requirement is more complex) which represent all the sub strings of length N for one (without actually creating those substrings) and use it to scan strings of length N for likely matches.

You could do this in O(M) time where M is the length of longest String.

You can create a substring class like this.

class Substring {
    final String s;
    final int offset, length, hashCode;

    Substring(String s, int offset, int length) {
        this.s = s;
        this.offset = offset;
        this.length = length;
        this.hashCode = hashCode(s, offset, length); // define to taste
    }

    public int hashCode() { return hashCode; }

    public boolean equals(Object o) {
       if (!(o instanceof Substring)) return false;
       Substring ss = (Substring) s;
       if (hashCode != ss.hashCode || length != ss.length) return false;
       for (int i = 0; i < length; i++) 
           if (s.charAt(i) != ss.s.charAt(i))
               return false;
       return true;
    }
}

To build the HashSet, you can do the following in O(n) where n is s1.length()

Set<Substring> substrings = new HashSet<>();
for (int i = 0; i < s1.length() - n; i++) {
    Substring ss = new Substring(s1, i, n);
    substrings.add(ss);
}

To do the search for matches, you can do the following in O(n) where n is s2.length()

for (int i = 0; i < s2.length() - n; i++) {
    Substring ss = new Substring(s2, i, n);
    if (substrings.contains(ss))
         return true; // found a match.
}

So, without contains, substring I am assuming you mean not to use any Java APIs. Here is an implementation using dynamic programming:

public static boolean hashCheated(String a, String b, int N) {
    int m = a.length();
    int n = b.length();

    int max = 0;

    int[][] dp = new int[m][n];

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(a.charAt(i) == b.charAt(j)){
                if(i==0 || j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j] = dp[i-1][j-1]+1;
                }

                if(max < dp[i][j])
                    max = dp[i][j];
            }

        }
    }

    return (max >= N);
}