Преобразование символов строки1 в символы из строки2 путем увеличения или уменьшения лексикографически

Для двух строк A и B , имеющих строчные буквы английского алфавита, задача состоит в том, чтобы найти количество операций, необходимых для преобразования строки A таким образом, чтобы она содержала только буквы, которые также есть в строке B , где при каждой операции текущий символ может быть изменен. либо к следующему символу, либо к предыдущему символу. Кроме того, следующий символ после « z » — это « a », а предыдущий символ после « a » — « z ».

Примеры :

Input: A = “abcd”, B = “bc”
Output: 2
Explanation: The given string A = “abcd” can be converted into the string “bbcc” by incrementing the 1st character of the string in 1st move and decrementing the last character in 2nd move. Hence, A = “bbcc” has all the characters that are also in string B. Therefore, the required number of moves is 2 which is the minimum possible.

Input: A = “abcde”, B = “yg”
Output: 14

Подход: Данную задачу можно решить с помощью жадного подхода. Идея состоит в том, чтобы преобразовать все символы в строке A, которых нет в строке B, в ближайший возможный символ, который существует в строке B, что можно сделать, выполнив следующие шаги:

• Сохраните частоту символов строки B в неупорядоченной карте m.
• Переберите заданную строку A и проверьте для каждого символа в B количество шагов, необходимых для преобразования текущего символа в него.
• Способы преобразования символа x в y могут быть двух разных типов:
  • Первый — увеличивать символ x до тех пор, пока не будет достигнуто значение y , т. ^е . вращение по часовой стрелке.
  • Второй — уменьшать символ x до тех пор, пока не будет достигнут y , т. ^е . вращение против часовой стрелки.
• Следовательно, сохраните сумму всех минимальных ходов по часовой стрелке и против часовой стрелки для каждого символа в A в переменной ans , которая является требуемым значением.

Ниже приведена реализация вышеуказанного подхода:

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