Минимальное количество операций приращения, необходимых для того, чтобы сделать две строки равными

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

Учитывая две строки S1 и S2 одинаковой длины, содержащие символы в диапазоне от «0» до «9», задача состоит в том, чтобы вернуть минимальное количество операций, необходимых для того, чтобы сделать две строки равными, выполнив следующие операции:

  • Увеличение любых двух символов из строки на 1.
  • Если невозможно сделать две строки равными вышеуказанному условию, верните -1.

Примеры:

Input : S1 = “12”, S2 = “21”
Output : 1
Explanation: Operation 1: Increment first index of S1 and 
second index of S2, new S1 = “22”, S2 = “22”

Input : “123”, S2 = “015”
Output : 2
Explanation: Operation 1: Increment third index of S1 and 
first index of S2, new S1 = “124”, S2 = “115”
Operation 2: Increment third index of S1 and second index of S2.
New S1 = “125”, S2 = “125”

Input: S1 = “19”, S2 = “24”
Output: -1
Explanation: There is no such valid operation exists through which 
we can make two strings equal.

Подход: Для решения проблемы выполните следующие наблюдения:

Наблюдения:

We are incrementing 1 to both the characters of strings to perform valid operation. So, if initially S1 and S2 have different sums, they can never be made equal (since they must have the same sum when they are equal). Now let, Sum(S1) = Sum(S2). Lets see for a specific index  
0 ≤ i ≤ N – 1(N is length of either string S1 or S2).

  • If S1[ i ] == s2[ i ], no operation will be needed
  • If s1[ i ] > S2[ i ], then we need to add S1[ i ] – S2[ i ] in S2 to make S1[ i ] and S2[ i ] equal.
  • If S1[ i ] < S2[ i ], then we need to add S2[ i ] – S1[ i ] in S1 to make S1[ i ] and S2[ i ] equal.

Let x is summation of S1[ i ] – S2[ i ] for all indices where S1[ i ] > S2[ i ]. As noted above, x is the minimum number of operations we need to perform on indices of S2.

Let y is summation of S2[ i ] – S1[ i ] for all indices where S1[ i ] < S2[ i ]. As noted above, y is the minimum number of operations we need to perform on indices of S1.

We will find the total summation of operations needed on both the strings i.e (x+y) and we will divide it by 2 because in every single operation we need to increase any character from both the strings.

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

Временная сложность: O( N ), где N — длина строки S1 или S2.
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ