*1.2K*

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:

- Find out all the sub-strings of first string.
- Find out all the sub-strings of second string.
- Once you have all the sub-strings, see if you can find any common sub-strings.
- 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:

- Add all the characters of
`str1`

to`setA`

. So,`setA`

would look like`setA = < b, a, r, e, l >`

- Add all the characters of
`str2`

to`setB`

. So,`setB`

would become`setB = < t, r, a, p, e >`

- Take an intersection of both the sets. An intersection should give you the common characters.
- After the intersection, you will get the common characters as:
`< a, r, e >`

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