Максимизируйте абсолютное смещение от начала координат, перемещаясь по оси X на основе заданных команд.

Дана строка S длины N, где каждый символ строки равен 'L', 'R' или '?' , задача состоит в том, чтобы найти максимальное абсолютное смещение от начала координат, перемещаясь по заданным командам по оси X, начиная с начала координат (0, 0) :

• 'L': переместиться на одну единицу в отрицательном направлении X.
• 'R': переместиться на одну единицу в положительном направлении X.
• '?': может переместиться на одну единицу в отрицательном или положительном направлении X.

Примеры:

Input: S = “LL??R” 
Output: 3
Explanation:
One of the possible way to move is:

1. S[0] = ‘L’, move one unit in -ve X direction, so displacement becomes equal to -1.
2. S[1] = ‘L’, move one unit in -ve X direction, so displacement becomes equal to -2.
3. S[2] = ‘?’, move one unit in -ve X direction, so displacement becomes equal to -3.
4. S[3] = ‘?’, move one unit in -ve X direction, so displacement becomes equal to -4.
5. S[4] = ‘R’, move one unit in +ve X direction, so displacement becomes equal to -3.

 Therefore, the absolute displacement is abs(-3)=3, and also it is the maximum absolute displacement possible.

Input: S = “?RRR?”
Output: 5

Наивный подход: самый простой способ решить проблему — попробовать заменить '?' с помощью «L» или «R», используя рекурсию, а затем напечатать максимальное полученное абсолютное смещение.

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

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

Эффективный подход: описанный выше подход может быть оптимизирован на основе наблюдения, что максимальное абсолютное смещение будет получено, когда '?' заменяется максимально встречающимся символом. Выполните следующие шаги, чтобы решить проблему:

• Найдите количество символов 'L' в S и сохраните его в переменной, скажем, l .
• Найдите количество символов 'R' в S и сохраните его в переменной, скажем, r .
• Выведите ответ в виде N – min(l, r)

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

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