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

[Anonymous]

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

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

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"

Здесь в dcd мы считаем, что в подстроке есть два разных символа: c и d, поэтому она считается допустимой подстрокой. .
Ниже приведен мой код. Для его решения я использовал метод скользящего окна, а для обеспечения уникальности я использовал 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 — длина строки (поправьте меня, если я ошибаюсь).
Временная сложность приведенного выше кода равна O(n^2), где n — длина строки (поправьте меня, если я ошибаюсь).
Временная сложность приведенного выше кода равна O(n^2), где n — длина строки (поправьте меня, если я ошибаюсь).
p>
Я хочу уменьшить временную сложность этого кода. Каков правильный подход?

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