Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки

Опубликовано: 27 Февраля, 2023

Для заданной строки S размера N задача состоит в том, чтобы найти количество подстрок нечетной длины, медиана которых равна K- му символу строки.

Примеры:

Input: S = “ecadgg”, K = 4
Output: 4
Explanation: Character at 4th position in string is ‘d’. 
Then there are 4 odd length substrings with ‘d’ as their median: 
[d], [a, d, g], [e, c, a, d, g], therefore return 4 as the answer.

Input: s = “abc”, K = 1
Output: 1
Explanation: Character at 1st position in string is ‘a’. Then there is only 1 odd length substring with ‘a’ as its median: [a] therefore return 1 as the answer.

Подход: Чтобы решить проблему, следуйте следующей идее:

Median is middle element. So smaller elements has to be equal to number of bigger elements, the desired substrings would be like (S[K]) or (2 elements on left and right), (4 elements on left and right), so on. . . [cannot take 1, 3 . . . because the substring should have odd length]

  • We can maintain smaller and bigger arrays of length N and populate them.
  • This helps us to find in range [i, j] count of smaller and bigger elements with respect to S[K]. 
    • For S[K] to be median in the range [i, j], the number of characters smaller than S[K] should be equal to the number of characters greater than S[K] and the subarray should include S[K].

Note: We are considering 1based indexing of string for understanding but the actual implementation uses 0 based indexing.

Следуйте инструкциям, чтобы решить проблему:

  • Создайте два вектора, а именно больший и меньший размера N.
  • Перебрать строку:
    • Отметить 1 в меньшем векторе в i позиции, если символ с этим индексом меньше, чем K символ строки, и
    • Отметьте 1 в большем векторе в i позиции, если символ больше, чем K символ строки.
  • Создайте массив разностей, в котором хранится разница меньшего и большего для каждой i- й позиции.
  • Используйте сумму префиксов в массиве разностей, чтобы найти допустимые подмассивы. В допустимых подмассивах сумма будет равна 0 .
    • Используйте сумму префикса для следующих трех сегментов:
      • start = 0 и end = N и сохраните их в val1 ,
      • start = 0 и end = K-1 сохраните его в val2 и
      • start = K и end = N и сохраните их в val3 .
  • В конце верните val1 – val2 – val3 , что является количеством подстрок с одинаковыми меньшими и большими элементами, которые содержат K- й символ.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)