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
str1tosetA. So,setAwould look likesetA = < b, a, r, e, l > - Add all the characters of
str2tosetB. So,setBwould becomesetB = < 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.
Video Explanation:
