Минимизируйте длину строки, удалив заданные последовательные пары

Для заданной строки S размера N , состоящей из символов от «0» до «9», задача состоит в том, чтобы минимизировать длину строки, где В каждой операции минимизации мы можем удалить любые два последовательных символа, если они имеют вид {“ 12", "21", "34", "43", "56", "65", "78", "87", "09", "90"}.

Примеры:

Input: S = “672183”
Output: 2
Explanation: 
perform the minimizing operation at index 2 and 3 “672183″, after the removal resultant string will be “6783”
perform the minimizing operation at index 1 and 2 “6783″, after the removal resultant string will be”63″
Since no further minimizing operation can be performed, the minimum possible length of the string is 2.

Input: S = “19532”
Output: 5
Explanation: No operation can be performed 

Подход:

Traverse through the string and keep removing the consecutive characters if they are in the above-mentioned form Break if there is no pair of characters found for minimizing return of the final length of the given string

• Создайте фиктивную временную строку для хранения результирующей строки.
• Начните обход заданной строки и проверьте, образует ли последний символ съемную пару с текущим символом, а затем удалите их обоих.
  • Чтобы проверить пары, создайте еще одну логическую функцию и проверьте, образуют ли два символа возможную пару для операции минимизации или нет.
    • Если да, вернуть true.
    • В противном случае вернуть ложь.
• Если размер фиктивной строки temp больше 0, а последний символ и текущий символ currChar составляют пару, удалите их.
  • В противном случае добавьте currChar в фиктивную временную строку.
• Возвращает длину временной строки.

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

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