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

0 0 7 minutes read

Given 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: 3
Explanation:
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: 5

Naive 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:

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
// Recursive function to find the maximum
// absolute displacement from origin by
// performing the given set of moves
int DistRecursion(string S, int i, int dist)
{
    // If i is equal to N
    if (i == S.length())
        return abs(dist);
 
    // If S[i] is equal to 'L'
    if (S[i] == 'L')
        return DistRecursion(S, i + 1, dist - 1);
 
    // If S[i] is equal to 'R'
    if (S[i] == 'R')
        return DistRecursion(S, i + 1, dist + 1);
 
    // If S[i] is equal to '?'
    return max(DistRecursion(S, i + 1, dist - 1),
               DistRecursion(S, i + 1, dist + 1));
}
// Function to find the maximum absolute
// displacement from the origin
 
int maxDistance(string S)
{
 
    // Return the maximum absolute
    // displacement
    return DistRecursion(S, 0, 0);
}
 
// Driver Code
int main()
{
    // Input
    string S = "?RRR?";
 
    // Function call
 
    cout << maxDistance(S);
    return 0;
}
 
// This code is contributed by lokesh potta.

Java

// Java program for the above approach
import java.util.*;
class GFG {
 
    // Recursive function to find the maximum
    // absolute displacement from origin by
    // performing the given set of moves
    static int DistRecursion(String S, int i, int dist)
    {
        char[] ch = S.toCharArray();
        // If i is equal to N
        if (i == ch.length)
            return Math.abs(dist);
 
        // If S[i] is equal to 'L'
        if (ch[i] == 'L')
            return DistRecursion(S, i + 1, dist - 1);
 
        // If S[i] is equal to 'R'
        if (ch[i] == 'R')
            return DistRecursion(S, i + 1, dist + 1);
 
        // If S[i] is equal to '?'
        return Math.max(DistRecursion(S, i + 1,
 
                                      dist - 1),
                        DistRecursion(S, i + 1, dist + 1));
    }
 
    // Function to find the maximum absolute
    // displacement from the origin
    static int maxDistance(String S)
    {
 
        // Return the maximum absolute
        // displacement
        return DistRecursion(S, 0, 0);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Input
        String S = "?RRR?";
 
        // Function call
        System.out.print(maxDistance(S));
    }
}
 
// This code is contributed by ukasp.

Python3

# Python3 program for the above approach
 
# Recursive function to find the maximum
# absolute displacement from origin by
# performing the given set of moves
 
 
def DistRecursion(S, i, dist):
 
    # If i is equal to N
    if i == len(S):
        return abs(dist)
 
    # If S[i] is equal to 'L'
    if S[i] == 'L':
        return DistRecursion(S, i + 1, dist-1)
 
    # If S[i] is equal to 'R'
    if S[i] == 'R':
        return DistRecursion(S, i + 1, dist + 1)
 
    # If S[i] is equal to '?'
    return max(DistRecursion(S, i + 1, dist-1),
               DistRecursion(S, i + 1, dist + 1))
 
 
# Function to find the maximum absolute
# displacement from the origin
def maxDistance(S):
 
    # Return the maximum absolute
    # displacement
    return DistRecursion(S, 0, 0)
 
# Driver Code
 
 
# Input
S = "?RRR?"
 
# Function call
print(maxDistance(S))

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Recursive function to find the maximum
// absolute displacement from origin by
// performing the given set of moves
static int DistRecursion(string S, int i, int dist)
{
     
    // If i is equal to N
    if (i == S.Length)
        return Math.Abs(dist);
 
    // If S[i] is equal to 'L'
    if (S[i] == 'L')
        return DistRecursion(S, i + 1, dist - 1);
 
    // If S[i] is equal to 'R'
    if (S[i] == 'R')
        return DistRecursion(S, i + 1, dist + 1);
 
    // If S[i] is equal to '?'
    return Math.Max(DistRecursion(S, i + 1,
                                   
                                  dist - 1),
                    DistRecursion(S, i + 1, dist + 1));
}
 
// Function to find the maximum absolute
// displacement from the origin
static int maxDistance(string S)
{
     
    // Return the maximum absolute
    // displacement
    return DistRecursion(S, 0, 0);
}
 
// Driver Code
public static void Main()
{
     
    // Input
    string S = "?RRR?";
 
    // Function call
    Console.Write(maxDistance(S));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Recursive function to find the maximum
// absolute displacement from origin by
// performing the given set of moves
function DistRecursion(S, i, dist) {
    // If i is equal to N
    if (i == S.length)
        return Math.abs(dist);
 
    // If S[i] is equal to 'L'
    if (S[i] == 'L')
        return DistRecursion(S, i + 1, dist - 1);
 
    // If S[i] is equal to 'R'
    if (S[i] == 'R')
        return DistRecursion(S, i + 1, dist + 1);
 
    // If S[i] is equal to '?'
    return Math.max(DistRecursion(S, i + 1, dist - 1),
        DistRecursion(S, i + 1, dist + 1));
}
// Function to find the maximum absolute
// displacement from the origin
 
function maxDistance(S) {
 
    // Return the maximum absolute
    // displacement
    return DistRecursion(S, 0, 0);
}
 
// Driver Code
 
// Input
let S = "?RRR?";
 
// Function call
 
document.write(maxDistance(S));
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output

Time Complexity: O(2^N)
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:

Find count of character ‘L’ in S, and store it in a variable say l.
Find count of character ‘R’ in S, and store it in a variable say r.
Print the answer as N – min(l, r)

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int count(string s, char c) {
    int ans = 0;
    for(int i = 0; i < s.length(); i++)
    {
        if (c == s[i])
        {
            ans++;
        }
    }
    return ans;
}
 
// Function to find the maximum absolute
// displacement from the origin
int maxDistance(string S) {
  
    // Stores the count of 'L'
    int l = count(S, 'L');
 
    // Stores the count of 'R'
    int r = count(S, 'R');
 
    // Stores the length of S
    int N = S.length();
 
    // Return the answer
    return abs(N - min(l, r));
}
     
int main()
{
    // Input
    string S = "?RRR?";
 
    // Function call
    cout << maxDistance(S);
 
    return 0;
}
 
// This code is contributed by divyesh072019.

Java

// Java program for the above approach
 
// Function to find the maximum absolute
// displacement from the origin
class GFG {
    static int maxDistance(String S) {
 
        // Stores the count of 'L'
        int l = count(S, 'L');
 
        // Stores the count of 'R'
        int r = count(S, 'R');
 
        // Stores the length of S
        int N = S.length();
 
        // Return the answer
        return Math.abs(N - Math.min(l, r));
 
    }
 
    private static int count(String s, char c) {
        int ans = 0;
        for (char i : s.toCharArray())
            if (c == i)
                ans++;
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args) {
 
        // Input
        String S = "?RRR?";
 
        // Function call
        System.out.println(maxDistance(S));
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program for the above approach
 
# Function to find the maximum absolute
# displacement from the origin
 
 
def maxDistance(S):
 
    # Stores the count of 'L'
    l = S.count('L')
 
    # Stores the count of 'R'
    r = S.count('R')
 
    # Stores the length of S
    N = len(S)
 
    # Return the answer
    return abs(N - min(l, r))
 
 
# Driver Code
 
# Input
S = "?RRR?"
 
# Function call
print(maxDistance(S))

C#

// C# program for the above approach
 
// Function to find the maximum absolute
// displacement from the origin
using System;  
 
public class GFG {
    static int maxDistance(String S) {
 
        // Stores the count of 'L'
        int l = count(S, 'L');
 
        // Stores the count of 'R'
        int r = count(S, 'R');
 
        // Stores the length of S
        int N = S.Length;
 
        // Return the answer
        return Math.Abs(N - Math.Min(l, r));
 
    }
 
    private static int count(String s, char c) {
        int ans = 0;
        foreach (char i in s.ToCharArray())
            if (c == i)
                ans=ans+1;
        return ans;
    }
 
    // Driver Code
    public static void Main(String[] args) {
 
        // Input
        String S = "?RRR?";
 
        // Function call
        Console.WriteLine(maxDistance(S));
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program for the above approach
 
// Function to find the maximum absolute
// displacement from the origin
    function maxDistance(S) 
    {
 
        // Stores the count of 'L'
        var l = count(S, 'L');
 
        // Stores the count of 'R'
        var r = count(S, 'R');
 
        // Stores the length of S
        var N = S.length;
 
        // Return the answer
        return Math.abs(N - Math.min(l, r));
 
    }
 
    function count(s, c) {
        var ans = 0;
        for (var i in s.split(''))
            if (c == i)
                ans++;
        return ans;
    }
 
// Driver Code
 
// Input
var S = "?RRR?";
 
// Function call
document.write(maxDistance(S));
 
// This code is contributed by 29AjayKumar 
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!