Split a String in Balanced Strings

🏠 ⬅️ ➡️

Balanced strings are those that have an equal quantity of 'L' and 'R' characters.

Given a balanced string s, split it into some number of substrings such that:

  • Each substring is balanced.

Return the maximum number of balanced strings you can obtain.

Example 1:

Input: s = "RLRRLLRLRL " Output: 4 Explanation: s can be split into "RL ", "RRLL ", "RL ", "RL ", each substring contains same number of 'L' and 'R'.

Example 2:

Input: s = "RLRRRLLRLL " Output: 2 Explanation: s can be split into "RL ", "RRRLLRLL ", each substring contains same number of 'L' and 'R'. Note that s cannot be split into "RL ", "RR ", "RL ", "LR ", "LL ", because the 2nd and 5th substrings are not balanced.

Example 3:

Input: s = "LLLLRRRR " Output: 1 Explanation: s can be split into "LLLLRRRR ".

Constraints:

  • 2 <= s.length <= 1000
  • s[i] is either 'L' or 'R'.
  • s is a balanced string.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=1000) :: s
    integer :: n, i, j, count_l, count_r

    read(*,*) s
    n = len(trim(s))

    do i = 1, n
        if (s(i:i) == 'L') then
            count_l = count_l + 1
        else if (s(i:i) == 'R') then
            count_r = count_r + 1
        end if
    end do

    if (count_l == count_r) then
        print *, 1
    else
        print *, 0
    end if

end program main
✅ Compiled
❌ Executed
❌ Correct 
program main
      implicit none

      integer :: i, j, k, n, m
      character(len=1000) :: s
      integer :: count_l, count_r
      integer :: max_balanced_strings

      ! Read input
      read(*,*) s

      ! Initialize variables
      n = len(s)
      count_l = 0
      count_r = 0
      max_balanced_strings = 0

      ! Iterate over the string
      do i = 1, n
          if (s(i:i) == 'L') then
              count_l = count_l + 1
          else if (s(i:i) == 'R') then
              count_r = count_r + 1
          end if

          ! Check if the current substring is balanced
          if (count_l == count_r) then
              max_balanced_strings = max_balanced_strings + 1
          end if
      end do

      ! Print output
      write(*,*) max_balanced_strings

      end program main
🌐 Data from online sources 
def find_special_integer(arr):
    n = len(arr)
    required_count = n // 4
    for i in range(n):
        if arr[i] == arr[i + required_count]:
            return arr[i]
    return -1

The algorithm iterates through the sorted array once. At each iteration, it compares the current integer with the integer that's "requiredCount" positions ahead (where "requiredCount" is the number of elements divided by 4). If the two integers are the same, it means that the integer occurs more than 25% of the time in the array, and it is returned. If no such integer is found, the algorithm returns -1, which should not happen according to the problem constraints. The time complexity is O(n), where n is the number of elements in the array.

🌐 Data from online sources 
int findSpecialInteger(const vector<int>& arr) {
    int n = arr.size(), requiredCount = n / 4;
    for (int i = 0; i < n; i++) {
        if (arr[i] == arr[i + requiredCount]) {
            return arr[i];
        }
    }
    return -1;
}

The algorithm iterates through the sorted array once. At each iteration, it compares the current integer with the integer that's "requiredCount" positions ahead (where "requiredCount" is the number of elements divided by 4). If the two integers are the same, it means that the integer occurs more than 25% of the time in the array, and it is returned. If no such integer is found, the algorithm returns -1, which should not happen according to the problem constraints. The time complexity is O(n), where n is the number of elements in the array.