[Hackerrank] – Two Strings Solution

Question: Given two strings, determine if they share a common sub-string.

Input: “a” and “art”

Output: YES

Problem Statement

Let me try to simplify this problem statement first.

You are given two strings, and you need to find out if they share a common sub-string or not. If you can find a common sub-string, output “YES”, else output “NO”. Note that you don’t have to find out what is the common sub-string.

Another important aspect of this problem is that the sub-string can be as small as 1 character. A sub-string is basically any string that can be formed using one or more characters of the original string.

Let us look at a sample test case:

So, if you are given with strings “CAT” and “RAT”, you can see that they share a common sub-string “AT”, hence in this case your answer should be “YES”

Brute Force Method:

One easy way to solve this problem would be:

1. Find out all the sub-strings of first string.
2. Find out all the sub-strings of second string.
3. Once you have all the sub-strings, see if you can find any common sub-strings.
4. Output “YES” or “NO” based upon your findings.

Note that, this method works fine, but you will waste a lot of time in finding out all the valid sub-strings. So, we need to find a way to optimize it somehow.

Efficient Method:

There is a very big hint hidden in the problem statement itself. The problem says that the sub-string could be as small as one character. So, you do not need even need to find out all the sub-strings. If you can find a common character, that should be all.

So let us assume you are given with two strings:

str1 = “barbell”
str2 = “trapper”

An efficient way to solve this problem could be:

1. Add all the characters of str1 to setA. So, setA would look like
   setA = < b, a, r, e, l >
2. Add all the characters of str2 to setB. So, setB would become
   setB = < t, r, a, p, e >
3. Take an intersection of both the sets. An intersection should give you the common characters.
4. After the intersection, you will get the common characters as:
   < a, r, e >
5. If you can find some characters after intersection, the result is “YES”, else “NO”.

Code:

  public String twoStrings(String s1, String s2) {

    Set<Character> s1Set = new HashSet<>();
    Set<Character> s2Set = new HashSet<>();

    //creating the set of string1
    for(char c : s1.toCharArray()) {
      s1Set.add(c);
    }
    //creating the set of string2
    for(char c : s2.toCharArray()) {
      s2Set.add(c);
    }

    // store the set intersection in s1Set
    s1Set.retainAll(s2Set);

    if (!s1Set.isEmpty())
      return "YES";

    return "NO";
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(1)
The full solution and test cases are also available on Github.

Video Explanation: