Given two strings, determine if they share a common substring. A substring may be as small as one character.
For example, the words "a", "and", "art" share the common substring . The words "be" and "cat" do not share a substring.
Function Description
Complete the function twoStrings in the editor below. It should return a string, either YES or NO based on whether the strings share a common substring.
twoStrings has the following parameter(s):
- s1, s2: two strings to analyze .
Input Format
The first line contains a single integer , the number of test cases.
The following pairs of lines are as follows:
- The first line contains string .
- The second line contains string .
Constraints
- and consist of characters in the range ascii[a-z].
Output Format
For each pair of strings, return YES or NO.
Sample Input
2
hello
world
hi
world
Sample Output
YES
NO
Explanation
We have pairs to check:
- , . The substrings and are common to both strings.
- , . and share no common substrings.
Solution:-
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the twoStrings function below.
static final int MAX_CHARS = 256;
static String findSubString(String str)
{
int n = str.length();
int dist_count = 0;
boolean[] visited = new boolean[MAX_CHARS];
Arrays.fill(visited, false);
for (int i = 0; i < n; i++) {
if (visited[str.charAt(i)] == false) {
visited[str.charAt(i)] = true;
dist_count++;
}
}
int start = 0, start_index = -1;
int min_len = Integer.MAX_VALUE;
int count = 0;
int[] curr_count = new int[MAX_CHARS];
for (int j = 0; j < n; j++) {
curr_count[str.charAt(j)]++;
if (curr_count[str.charAt(j)] == 1)
count++;
if (count == dist_count) {
while (curr_count[str.charAt(start)] > 1) {
if (curr_count[str.charAt(start)] > 1)
curr_count[str.charAt(start)]--;
start++;
}
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
return str.substring(start_index, start_index + min_len);
}
static String twoStrings(String str, String str1) {
String a=findSubString(str);
String b=findSubString(str1);
String s="NO";
for(int i=0;i<a.length();i++)
{
for(int j=0;j<b.length();j++)
{
if(a.charAt(i)==(b.charAt(j)))
{
s="YES";
break;
}
}
if(s.equals("YES"))
break;
}
return s;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int q = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int qItr = 0; qItr < q; qItr++) {
String s1 = scanner.nextLine();
String s2 = scanner.nextLine();
String result = twoStrings(s1, s2);
bufferedWriter.write(result);
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
