Skip to content

Given two strings, determine if they share a common substring

This is my first Question here, I need to know why the following code does not pass Sample test case 2 in hacker rank-> Algorithms-> Strings-> Two Strings: The question is here: https://www.hackerrank.com/challenges/two-strings/problem

public static String twoStrings(String s1, String s2) {
        String answer = ""; 
        String StringToIterate = "";
        String theOtherString = "";
    
        if (s1.length() > s2.length()) {
            StringToIterate = s2;
            theOtherString  = s1;
        } else if (s1.length() < s2.length()){
            StringToIterate = s1;
            theOtherString = s2;
        } else {
            StringToIterate = s1;
            theOtherString = s2;
        }
    
    for (int i= 0; i < StringToIterate.length();i++) {
         String subS = StringToIterate.substring(i);
         if (theOtherString.contains(subS)) {
            answer = "YES";
        } else {
            answer = "NO";
       }
   }
   return answer;
   }
}

Sample test case 2:
2

aardvark

apple

beetroot

sandals

my code gives: No No but the expected output is: Yes No

Answer

I’m assuming one of the test cases uses a fairly large string with a lot of duplicate letters. You can try editing your solution to keep track of substrings you’ve already checked. For example:

public static String twoStrings(String s1, String s2) {
    String answer = ""; 
    String StringToIterate = "";
    String theOtherString = "";

    List<String> checked = new ArrayList<>();

    if (s1.length() > s2.length()) {
        StringToIterate = s2;
        theOtherString  = s1;
    } else if (s1.length() < s2.length()){
        StringToIterate = s1;
        theOtherString = s2;
    } else {
        StringToIterate = s1;
        theOtherString = s2;
    }

    for (int i= 0; i < StringToIterate.length();i++) {
        String subS = StringToIterate.substring(i,i+1);
        if (checked.contains(subS)) {
            continue;
        }

        if (theOtherString.contains(subS)) {
            answer = "YES";
            break;
        } else {
            checked.add(subS);
            answer = "NO";
        }
    }

    return answer;
}

Running your function with the checked List does not run into the time limit.

But this got me thinking “a Stream can do all of this” and that had me solving this problem in a completely different manner:

public static String twoStrings(String s1, String s2) {
    return s1.chars()
             .distinct()
             .mapToObj(c -> String.valueOf((char)c))
             .anyMatch(s2::contains) ? "YES" : "NO";
}

Without the .distinct() step I also get a timeout on tests 4 and 5, but with it all tests pass reasonably quickly.