Найти символы, которые при увеличении на K присутствуют в строке
Дана строка s строчных букв английского алфавита и целое число K . задача состоит в том, чтобы проверить, присутствует ли в строке каждый символ после увеличения их ASCII на K или нет. Возвращает только уникальные символы и первый индекс, в котором они присутствуют.
Примеры:
Input: s = “dszepvaxuo”, k = 3
Output: {{1, ‘s’}, {6, ‘a’}, {8, ‘u’}}
Explanation: Moving each character 3 steps gives:
‘d’ -> ‘g’, ‘g’ is not present in s
‘s’ -> ‘v’, ‘v’ is present in s, thus, indices array becomes{{1, ‘s’}}
‘z’ -> ‘c’, ‘c’ is not present in s
‘e’ -> ‘h’, ‘h’ is not present in s
‘p’ -> ‘s’, ‘s’ is present in s, but is already present in indices array
‘v’ -> ‘y’, ‘y’ is not present in s
‘a’ -> ‘d’, ‘d’ is present in s, thus, indices array becomes {{1, ‘s’}. {6, ‘a’}}
‘x’ -> ‘a’, ‘a’ is present in s, but is already present in indices array
‘u’ -> ‘x’, ‘x’ is present in s, thus, indices array becomes {{1, ‘s’}, {6, ‘a’}, {8, ‘u’}}
‘o’ -> ‘r’, ‘r’ is not present in s
Thus, final indices array is {{1, ‘s’}, {6, ‘a’}, {8, ‘u’}}Input: s = “abcdefg”, k = 2
Output: {{0, ‘a’}, {1, ‘b’}, {4, ‘e’}}
Подход: Подход к решению проблемы следующий:
Store each character in a data structure (like set) for easy look up. Iterate over the string, check for each character if it satisfies the condition and is and add valid character’s indices to the output array if that character is not considered already.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N * log(N))
Вспомогательное пространство: O(N)