Given two strings, determine if they share a common substring-CodePudding

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

CodePudding user response：

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.

CodePudding user response：

To get this sample case working I would suggest replacing answer = "YES"; with return "YES";.

There only has to be one substring that matches. Therefore, you should stop searching when you have found a match. Your code will happily continue searching through other substrings, even if you already found a match, and thereby setting the answer back to NO.

I don't know what the exact assignment was, but it seems that you also have to look at internal substrings. Your code only looks at the first i letters of StringToIterate.

I try to explain it using your sample case: Your code will substring check these strings

a
ap
app
appl
apple

However, p or le could've also been substrings of aardvark. Try to change your code to also check these substrings.

I hope this is enough information to keep on coding and good luck with your assignment!

CodePudding user response：

problem solved and The initial Test cases passed by doing the suggestions given by the commenters:adding break; after "YES" and use substring(i,i 1). However, when I submitted the code after suggested corrections, I got "Time limit exceeded" 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,i 1);
         if (theOtherString.contains(subS)) {
            answer = "YES";
            break;
        } else {
            answer = "NO";
       }
   }
   return answer;
   }
}

Also, I cannot add return inside the for loop/if statement,because the compiler of course wants a return in the method body but outside the for loop. So, any suggestion?