Question

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.

Answer 1

The reason for the timeout is probably: to compare two strings that each are 1.000.000 characters long, your code needs 1.000.000 * 1.000.000 comparisons, always.

There is a faster algorithm that only needs 2 * 1.000.000 comparisons. You should use the faster algorithm instead. Its basic idea is:

for each character in s1: add the character to a set (this is the first million)

for each character in s2: test whether the set from step 1 contains the character, and if so, return "yes" immediately (this is the second million)

Java already provides a BitSet data type that does all you need. It is used like this:

Bit Set seen In S1 = new Bit Set();

seen In S1. set('x');

seen InS1. get('x');

please mark it as a brainlist please plz