Проверка и оптимизация кода - двухстрока общая подстрока

Question

Я решал проблему с двумя строками. Я написал ниже код. Он прошел 4 тестовых случая, но для двух тестовых случаев он показал время ожидания. Пожалуйста, дайте мне знать, как я могу оптимизировать его, чтобы избежать тайм-аутов? Также приветствуются любые ссылки, которые объясняют и показывают примеры такой оптимизации.

  public class TwoStrings
{
     private static final String YES = "YES";
private static final String NO  = "NO";

public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int testCases = Integer.parseInt(in.nextLine());
String input1[] = new String[testCases];
String input2[] = new String[testCases];

for (int i = 0; i < testCases; i++)
{
    input1[i] = in.nextLine();
    input2[i] = in.nextLine();
}
in.close();

for (int i = 0; i < testCases; i++)
{
    displayResult(input1[i], input2[i]);
}
}

private static void displayResult(String string1, String string2)
{
// choosing smaller String for iterating through it.
String smallerString = string1.length() <= string2.length() ? string1
    : string2;
String biggerString = string1 == smallerString ? string2 : string1;

boolean constains = false;

// Concept - Even if single letter is common, substring exists.
// So checking just one string.
for (int i = 0; i < smallerString.length(); i++)
{
    if (biggerString.contains(String.valueOf(smallerString.charAt(i))))
    {
    constains = true;
    break;
    }
}

if (constains)
    System.out.println(YES);
else
    System.out.println(NO);
}
}

Answer 1

То, что вы сейчас делаете, это O(n^2), потому что вы перебираете небольшую строку, и поиск этого символа в более длинной строке является линейным поиском, потому что он не отсортирован (все буквы в алфавитном порядке).

Ниже приведено решение O(n). Идея состоит в том, чтобы иметь логический массив размера 26 (по одному на каждую букву) и сделать индекс истинным, если буква находится в маленькой (может быть маленькой или длинной строке, не имеет значения) строке. Создание массива из маленькой строки - это O(n), а проверка букв в длинной строке - это O(n), в результате получается общий итог O(n + n), который уменьшается до O(n).

private static void displayResult(String string1, String string2)
{
    boolean[] contains = new boolean[26];
    boolean noSubstring = true;

    // populate the contains array
    for (char c : string1.toCharArray())
    {
        int value = (int)c - (int)'a';    // make the char 0-25
        contains[value] = true;
    }

    for (char c : string2.toCharArray())
    {
        int value = (int)c - (int)'a';    // make the char 0-25

        if (contains[value])
        {
            noSubstring = false;
            break;
        }
    }

    if (noSubstring)   System.out.println("NO");
    else               System.out.println("YES");
}