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

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

Примеры:

Input: S = “ecadgg”, K = 4
Output: 4
Explanation: Character at 4^th 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 1^st 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)