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 movesint 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 originint maxDistance(string S){ // Return the maximum absolute // displacement return DistRecursion(S, 0, 0);}// Driver Codeint 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 approachimport 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 movesdef 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 origindef maxDistance(S): # Return the maximum absolute # displacement return DistRecursion(S, 0, 0)# Driver Code# InputS = "?RRR?"# Function callprint(maxDistance(S)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Recursive function to find the maximum// absolute displacement from origin by// performing the given set of movesstatic 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 originstatic int maxDistance(string S){ // Return the maximum absolute // displacement return DistRecursion(S, 0, 0);}// Driver Codepublic 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 movesfunction 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 originfunction maxDistance(S) { // Return the maximum absolute // displacement return DistRecursion(S, 0, 0);}// Driver Code// Inputlet S = "?RRR?";// Function calldocument.write(maxDistance(S));// This code is contributed by _saurabh_jaiswal</script> |
Output
5
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:
- 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 originint 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 originclass 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 origindef 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# InputS = "?RRR?"# Function callprint(maxDistance(S)) |
C#
// C# program for the above approach// Function to find the maximum absolute// displacement from the originusing 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// Inputvar S = "?RRR?";// Function calldocument.write(maxDistance(S));// This code is contributed by 29AjayKumar </script> |
Output
5
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
