Máximo de particiones de strings equilibradas

Dada una string balanceada str de tamaño N con un número igual de L y R , la tarea es encontrar un número máximo X , tal que una string dada pueda dividirse en X substrings balanceadas. Una string llamada a estar balanceada si el número de ‘L’s en la string es igual al número de ‘R’s . 
Ejemplos: 
 

Entrada: str = “LRLLRRLRRL” 
Salida: 4 
Explicación: { “LR”, “LLRR”, “LR”, “RL”} son las particiones posibles.
Entrada: “LRRRRLLRLLRL” 
Salida: 3 
Explicación: {“LR”, “RRRLLRLL”, “RL”} son las particiones posibles. 
 

Enfoque: El enfoque para resolver este problema es recorrer la string y seguir incrementando el conteo de L y R siempre que se encuentre. En cualquier instante en que las cuentas respectivas de L y R sean iguales, se forma un paréntesis equilibrado. Por lo tanto, el recuento de tales instancias da las particiones posibles máximas deseadas.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find a maximum number X, such
// that a given string can be partitioned
// into X substrings that are each balanced
#include <bits/stdc++.h>
using namespace std;
 
// Function to find a maximum number X, such
// that a given string can be partitioned
// into X substrings that are each balanced
int BalancedPartition(string str, int n)
{
 
    // If the size of the string is 0,
    // then answer is zero
    if (n == 0)
        return 0;
 
    // variable that represents the
    // number of 'R's and 'L's
    int r = 0, l = 0;
 
    // To store maximum number of
    // possible partitions
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
 
        // increment the variable r if the
        // character in the string is 'R'
        if (str[i] == 'R') {
            r++;
        }
 
        // increment the variable l if the
        // character in the string is 'L'
        else if (str[i] = 'L') {
            l++;
        }
 
        // if r and l are equal,
        // then increment ans
        if (r == l) {
            ans++;
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    string str = "LLRRRLLRRL";
 
    int n = str.size();
 
    // Function call
    cout << BalancedPartition(str, n) << endl;
 
    return 0;
}

// Java program to find a maximum number X, such
// that a given String can be partitioned
// into X subStrings that are each balanced
import java.util.*;
 
class GFG{
 
// Function to find a maximum number X, such
// that a given String can be partitioned
// into X subStrings that are each balanced
static int BalancedPartition(String str, int n)
{
     
    // If the size of the String is 0,
    // then answer is zero
    if (n == 0)
        return 0;
 
    // Variable that represents the
    // number of 'R's and 'L's
    int r = 0, l = 0;
 
    // To store maximum number of
    // possible partitions
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
         
       // Increment the variable r if the
       // character in the String is 'R'
       if (str.charAt(i) == 'R')
       {
           r++;
       }
        
       // Increment the variable l if the
       // character in the String is 'L'
       else if (str.charAt(i) == 'L')
       {
           l++;
       }
        
       // If r and l are equal,
       // then increment ans
       if (r == l)
       {
           ans++;
       }
    }
     
    // Return the required answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    String str = "LLRRRLLRRL";
    int n = str.length();
 
    // Function call
    System.out.print(BalancedPartition(str, n) + "\n");
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to find a maximum number X,
# such that a given string can be partitioned
# into X substrings that are each balanced
 
# Function to find a maximum number X, such
# that a given string can be partitioned
# into X substrings that are each balanced
def BalancedPartition(str1, n):
     
    # If the size of the string is 0,
    # then answer is zero
    if (n == 0):
        return 0
 
    # Variable that represents the
    # number of 'R's and 'L's
    r = 0
    l = 0
 
    # To store maximum number of
    # possible partitions
    ans = 0
 
    for i in range(n):
         
        # Increment the variable r if the
        # character in the string is 'R'
        if (str1[i] == 'R'):
            r += 1
 
        # Increment the variable l if the
        # character in the string is 'L'
        elif (str1[i] == 'L'):
            l += 1
 
        # If r and l are equal,
        # then increment ans
        if (r == l):
            ans += 1
 
    # Return the required answer
    return ans
 
# Driver code
if __name__ == '__main__':
     
    str1 = "LLRRRLLRRL"
    n = len(str1)
 
    # Function call
    print(BalancedPartition(str1, n))
 
# This code is contributed by Bhupendra_Singh

// C# program to find a maximum number X, such
// that a given String can be partitioned
// into X subStrings that are each balanced
using System;
class GFG{
 
// Function to find a maximum number X, such
// that a given String can be partitioned
// into X subStrings that are each balanced
static int BalancedPartition(string str, int n)
{
     
    // If the size of the String is 0,
    // then answer is zero
    if (n == 0)
        return 0;
 
    // Variable that represents the
    // number of 'R's and 'L's
    int r = 0, l = 0;
 
    // To store maximum number of
    // possible partitions
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
         
        // Increment the variable r if the
        // character in the String is 'R'
        if (str[i] == 'R')
        {
            r++;
        }
             
        // Increment the variable l if the
        // character in the String is 'L'
        else if (str[i] == 'L')
        {
            l++;
        }
             
        // If r and l are equal,
        // then increment ans
        if (r == l)
        {
            ans++;
        }
    }
     
    // Return the required answer
    return ans;
}
 
// Driver code
public static void Main()
{
    string str = "LLRRRLLRRL";
    int n = str.Length;
 
    // Function call
    Console.Write(BalancedPartition(str, n) + "\n");
}
}
 
// This code is contributed by Nidhi_Biet

<script>
    // Javascript program to find a maximum number X, such
    // that a given String can be partitioned
    // into X subStrings that are each balanced
     
    // Function to find a maximum number X, such
    // that a given String can be partitioned
    // into X subStrings that are each balanced
    function BalancedPartition(str, n)
    {
 
        // If the size of the String is 0,
        // then answer is zero
        if (n == 0)
            return 0;
 
        // Variable that represents the
        // number of 'R's and 'L's
        let r = 0, l = 0;
 
        // To store maximum number of
        // possible partitions
        let ans = 0;
        for(let i = 0; i < n; i++)
        {
 
           // Increment the variable r if the
           // character in the String is 'R'
           if (str[i] == 'R')
           {
               r++;
           }
 
           // Increment the variable l if the
           // character in the String is 'L'
           else if (str[i] == 'L')
           {
               l++;
           }
 
           // If r and l are equal,
           // then increment ans
           if (r == l)
           {
               ans++;
           }
        }
 
        // Return the required answer
        return ans;
    }
     
    let str = "LLRRRLLRRL";
    let n = str.length;
  
    // Function call
    document.write(BalancedPartition(str, n) + "</br>");
     
    // This code is contributed by divyeshrabadiya07.
 
</script>

4

Complejidad de tiempo: O(N)  
Complejidad de espacio: O(1)