- frequency-counting, Mathematical, Recursion

Maximize absolute displacement from origin by moving on X-axis based on given commands

Maximize absolute displacement from origin by moving on X-axis based on given commandsGiven a string S of length N, where each character of the string is either equal to ‘L’, ‘R’ or ‘?’, the task is to find the maximum absolute displacement from the origin by moving following the given commands on X-axis starting from the origin (0, 0):‘L’: Move one unit in the negative X direction.‘R’: Move one unit in the positive X direction.‘?’: Can either move one unit in the negative X or the positive X direction.Examples:Input: S = “LL??R” Output: 3Explanation:One of the possible way to move is:S[0] = ‘L’, move one unit in -ve X direction, so displacement becomes equal to -1.S[1] = ‘L’, move one unit in -ve X direction, so displacement becomes equal to -2.S[2] = ‘?’, move one unit in -ve X direction, so displacement becomes equal to -3.S[3] = ‘?’, move one unit in -ve X direction, so displacement becomes equal to -4.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: 5Naive Approach: The simplest approach to solve the problem is to try replacing ‘?’ with either ‘L’ or ‘R’ using recursion and then print the maximum absolute displacement obtained.Below is the implementation of the above approach:Python3      def DistRecursion(S, i, dist):          if i == len(S):        return abs(dist)          if S[i] == ‘L’:        return DistRecursion(S, i + 1, dist-1)          if S[i] == ‘R’:        return DistRecursion(S, i + 1, dist + 1)          return max(DistRecursion(S, i + 1, dist-1),               DistRecursion(S, i + 1, dist + 1))    def maxDistance(S):              return DistRecursion(S, 0, 0)      S = “?RRR?”  print(maxDistance(S))Time Complexity: O(2N)Auxiliary Space: O(1)Efficient Approach: The above approach can be optimized based on the observation that the maximum absolute displacement will be obtained when ‘?’ is replaced with maximum occurring character. Follow the steps below to solve the problem:Below is the implementation of the above approach:Python3      def maxDistance(S):          l = S.count(‘L’)          r = S.count(‘R’)          N = len(S)          return abs(N – min(l, r))      S = “?RRR?”  print(maxDistance(S))Time Complexity: O(N)Auxiliary Space: O(1)Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.