Home Strings [Hackerrank] – Two Strings Solution

[Hackerrank] – Two Strings Solution

0 comment

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()) {
}
//creating the set of string2
for(char c : s2.toCharArray()) {
}

// 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.

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More