Question: Given two strings, determine if they share a common sub-string. If they have a common sub-string, print YES else print NO.
Input:
studyalgorithms
algos
Output: YES
This is one of the easy problems but can get a little tricky, if we do not understand it completely. Let us try to understand the test case
String 1 = “studyalgorithms”
String 2 = “algos”
The sub-string “algo” is common between both the sub-strings and therefore the answer is “YES“.
Let us try to take one more test case.
String 1 = “hello”
String 2 = “world”
The answer would still be “YES“, because “o” and “l” are still strings even though they are single characters.
Here is an example of a test case where the output would be “NO“
String 1 = “hi”
String 2 = “alex”
There is no common sub-string between them.
Thus here are two concepts involved in solving this challenge:
- Understanding that a single character is a valid sub-string.
- Deducing that we only need to know that the two strings have a common sub-string — we don’t need to know what that sub-string is.
Thus, the key to solving this challenge is determining whether or not the two strings share a common character.
To do this, we create two sets, ‘a’ and ‘b’, where each set contains the unique characters that appear in the string it’s named after. Because sets don’t store duplicate values, we know that the size of our sets will never exceed the letters of the English alphabet. In addition, the small size of these sets makes finding the intersection very quick.
If the intersection of the two sets is empty, we print NO on a new line; if the intersection of the two sets is not empty, then we know that strings and share one or more common characters and we print YES on a new line.
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
* Created by studyalgorithms.com
*/
public class TwoStrings {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Set<Character> a;
Set<Character> b;
for (int i = 0; i < n; i++) {
a = new HashSet<>();
b = new HashSet<>();
for (char c : scan.next().toCharArray()) {
a.add(c);
}
for (char c : scan.next().toCharArray()) {
b.add(c);
}
// store the set intersection in set 'a'
a.retainAll(b);
System.out.println((a.isEmpty()) ? "NO" : "YES");
}
scan.close();
}
}
Code language: Java (java)A working implementation of the code can be found here.
This problem is also available on Hackerrank.