Подсчитать количество допустимых подстрок на основе предоставленного двоичного массива ⇐ JAVA

[Anonymous]

У меня есть строка s и массив целых чисел с именем nums, содержащий только 0 и 1, размер массива — 26, который представляет строчные английские буквы.Для данного индекса i, если nums = 0, означает, что символ алфавита i является слабым, если он равен 1, то символ алфавита в позиции i является сильным.
Найдите допустимое количество уникальных подстрок из s, таких, что количество слабых символов для этой подстроки не превышает k< /code> порог.
Пример:

Код: Выделить всё

s = "cdcdcd"
nums = [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
k = 1

Выход:

Код: Выделить всё

5

Объяснение:

Код: Выделить всё

Here are the 5 unique substrings:
"c"
"cd"
"d"
"dc"
"dcd"

Вот мой код, для его решения я использовал подход скользящего окна, для сохранения уникальности я использовал HashSet

Код: Выделить всё

import java.util.HashSet;
import java.util.Set;

public class Main {

public static int solve(String s, int[] nums, int k) {
Set set = new HashSet();

for (int i = 0; i < s.length(); i++) {
int weak = 0;

// Expand the window
for (int j = i; j < s.length(); j++) {
char ch = s.charAt(j);
// Check the current character for weak or strong
if (nums[ch - 'a'] == 0) {
weak++;
}

// If the number of weak characters exceeds k, break loop
if (weak > k) {
break;
}

// valid substring to the set
set.add(s.substring(i, j + 1));
}
}
return set.size();
}

public static void main(String[] args) {
int[] nums = {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
System.out.println(solve("cdcdcd", nums, 1));  // Output: 5
}
}

Временная сложность приведенного выше кода равна O(n^2), где n — длина строки.
Я хочу уменьшить временную сложность этого кода. Каков правильный подход?

Подробнее здесь: https://stackoverflow.com/questions/790 ... nary-array