Maximice el desplazamiento absoluto desde el origen moviéndose en el eje X según los comandos dados

Dada una string S de longitud N, donde cada carácter de la string es igual a ‘L’, ‘R’ o ‘?’ , la tarea es encontrar el desplazamiento absoluto máximo desde el origen moviéndose siguiendo los comandos dados en el eje X comenzando desde el origen (0, 0) :

• ‘L’: Mueve una unidad en la dirección X negativa.
• ‘R’: Mueve una unidad en la dirección X positiva.
• ‘?’: Puede mover una unidad en la dirección X negativa o X positiva.

Ejemplos:

Entrada: S = “LL??R” 
Salida: 3
Explicación:
Una de las posibles formas de moverse es:

1. S[0] = ‘L’, mueve una unidad en la dirección -ve X, de modo que el desplazamiento sea igual a -1.
2. S[1] = ‘L’, mueve una unidad en la dirección -ve X, de modo que el desplazamiento sea igual a -2.
3. S[2] = ‘?’, mueve una unidad en la dirección -ve X, de modo que el desplazamiento sea igual a -3.
4. S[3] = ‘?’, mueve una unidad en la dirección -ve X, de modo que el desplazamiento sea igual a -4.
5. S[4] = ‘R’, mueve una unidad en la dirección +ve X, de modo que el desplazamiento sea igual a -3.

 Por lo tanto, el desplazamiento absoluto es abs(-3)=3, y también es el máximo desplazamiento absoluto posible.

Entrada: S = “?RRR?”
Salida: 5

Enfoque ingenuo: el enfoque más simple para resolver el problema es intentar reemplazar ‘?’ con ‘L’ o ‘R’ usando recursividad y luego imprima el máximo desplazamiento absoluto obtenido.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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

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

5

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar basándose en la observación de que el desplazamiento absoluto máximo se obtendrá cuando ‘?’ se reemplaza con el carácter máximo que ocurre . Siga los pasos a continuación para resolver el problema:

• Encuentre el recuento del carácter ‘L’ en S y guárdelo en una variable, digamos l .
• Encuentre el recuento del carácter ‘R’ en S y guárdelo en una variable, digamos r .
• Imprime la respuesta como N – min(l, r)

A continuación se muestra la implementación del enfoque anterior:

// 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 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

# 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# 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

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

5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)