Two and a sub string

Question

Challenge:

Given two strings, A and B. Find if there is a substring that appears in both A and B.

Specifications:

Several test cases will be given to you in a single file. The first line of the input will contain a single integer T, the number of test cases.

Then there will be T descriptions of the test cases. Each description contains two lines. The first line contains the string A and the second line contains the string B.

For each test case, display YES (in a newline), if there is a common substring.
Otherwise, display NO.

Implementation:

import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class TwoStrings {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        for (int i = Integer.parseInt(input.nextLine()); i> 0; i--) {
            String sub1 = toDiscreteString(input.nextLine());
            String sub2 = toDiscreteString(input.nextLine());
            boolean success;
            if (sub1.length() < sub2.length()) {
                success = hasCommonSubString(sub1, sub2);
            } else {
                success = hasCommonSubString(sub2, sub1);
            }
            System.out.println(success ? "YES" : "NO");
        }
    }

    private static boolean hasCommonSubString(String shorter, String longer) {
        for (int i = 0; i < shorter.length(); i++) {
            if (longer.indexOf(shorter.charAt(i)) > -1) {
                return true;
            }
        }
        return false;
    }

    private static String toDiscreteString(String input) {
        Set<Character> set = new HashSet<>();
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            if (set.add(input.charAt(i))) {
                result.append(input.charAt(i));
            }
        }
        return result.toString();
    }
}

This is a challenge found on HackerRank and passes all test cases. Is there a more efficient method? Is this overly-convoluted? Java 8 is available.

Answer 1

Improve encapsulation

This piece of code inside main is a bit unfortunate:

boolean success;
if (sub1.length() < sub2.length()) {
    success = hasCommonSubString(sub1, sub2);
} else {
    success = hasCommonSubString(sub2, sub1);
}

The main method has an almost straightforward nice flow:

1. parse input
2. get result
3. print result

But only almost, because the code snippet above breaks it, by mixing in some logic.

It would be better if hasCommonSubString encapsulated all of the logic. Currently the logic is split between two places:

• The main logic is inside hasCommonSubString
• The logic of ordering the parameters by length is inside main

The problem with this split becomes obvious when you try to write test cases for the method.

Consider this alternative:

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    for (int i = Integer.parseInt(input.nextLine()); i> 0; i--) {
        String s1 = toDiscreteString(input.nextLine());
        String s2 = toDiscreteString(input.nextLine());
        boolean success = hasCommonSubString(s1, s2);
        System.out.println(success ? "YES" : "NO");
    }
}

private static boolean hasCommonSubString(String s1, String s2) {
    if (s1.length() < s2.length()) {
        return hasCommonSubStringHelper(s1, s2);
    }
    return hasCommonSubStringHelper(s2, s1);
}

I also renamed the variables sub1, and sub2, as "sub" seems to suggest sub-strings, but these are really just simply strings.

Improve performance

It's a pity to convert a String to a Set<Character> and then convert that back to String, to perform \$O(n)\$ lookups on it. You could just use the Set<Character>, no need to convert that to String, and that will allow \$O(1)\$ lookups.

Also note that you don't need to convert both parameters. One of them is enough. You can iterate over the other one in a single pass.

Lastly, instead of the repeated .charAt calls in this code, it would be better to save in a local variable and reuse:

if (set.add(input.charAt(i))) {
    result.append(input.charAt(i));
}

Answer 2

I am guessing indexOf is O(n). A faster way may be to add all the characters of a string to a set. Then call contains for each character of the second string (I would imagine that contains is on average O(1) for a hash set or O(lg(n)) for a tree set.)

private static boolean hasCommonSubString(String shorter, String longer)  
{

    Set<Integer> set = shorter.chars()
                              .boxed()
                              .collect(Collectors.toSet());

    return longer.chars().anyMatch(set::contains);    
}