Maximum Score After Splitting a String

🏠 ⬅️ ➡️

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101 " Output: 5 Explanation: All possible ways of splitting s into two non-empty substrings are: left = "0 " and right = "11101 ", score = 1 + 4 = 5 left = "01 " and right = "1101 ", score = 1 + 3 = 4 left = "011 " and right = "101 ", score = 1 + 2 = 3 left = "0111 " and right = "01 ", score = 1 + 1 = 2 left = "01110 " and right = "1 ", score = 2 + 1 = 3

Example 2:

Input: s = "00111 " Output: 5 Explanation: When left = "00 " and right = "111 ", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111 " Output: 3

Constraints:

  • 2 <= s.length <= 500
  • The string s consists of characters '0' and '1' only.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=500) :: s
    integer :: i, j, n
    integer :: max_score

    ! read input
    read(*,*) s

    ! find the maximum score
    max_score = -1
    do i = 1, len(s)-1
        do j = i+1, len(s)
            if (s(i:j) /= '0' .and. s(i:j) /= '1') cycle
            n = count(s(i:j) == '0') + count(s(i:j) == '1')
            if (n > max_score) max_score = n
        end do
    end do

    ! print output
    write(*,*) max_score

end program main
❌ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
character(len=500) :: s
integer :: left, right, score

! Read input
read(*,*) s

! Initialize variables
left = 0
right = 0
score = 0

! Loop through the string
do i = 1, len(s)
    if (s(i:i) == '0') then
        left = left + 1
    else
        right = right + 1
    end if
end do

! Calculate the score
score = left + right

! Print the result
write(*,*) score

end
🌐 Data from online sources 
from collections import Counter

def is_possible_divide(nums: List[int], k: int) -> bool:
    counts = Counter(nums)

    for key in sorted(counts):
        if counts[key] > 0:
            for i in range(k-1, -1, -1):
                if counts[key+i] < counts[key]:
                    return False
                counts[key+i] -= counts[key]

    return True
  1. Create a count map that counts the occurrences of each integer in the input array.
  2. Iterate through the keys in ascending order.
  3. For each key, if its value is greater than 0, try to find k-1 integers that are consecutive to the current integer.
  4. While iterating the keys, check if the occurrences of all consecutive integers are equal to or greater than the occurrences of the current integer. If not, return false as it isn't possible to divide the array into sets of k consecutive numbers. If everything passes through, return true.
🌐 Data from online sources 
#include <map>

bool isPossibleDivide(std::vector<int>& nums, int k) {
    std::map<int, int> counts;
    for (int num : nums) counts[num]++;

    for (auto it = counts.begin(); it != counts.end(); ++it) {
        if (it->second > 0) {
            for (int i = k - 1; i >= 0; --i) {
                if ((counts[it->first + i] -= it->second) < 0) return false;
            }
        }
    }

    return true;
}
  1. Create a count map that counts the occurrences of each integer in the input array.
  2. Iterate through the keys in ascending order.
  3. For each key, if its value is greater than 0, try to find k-1 integers that are consecutive to the current integer.
  4. While iterating the keys, check if the occurrences of all consecutive integers are equal to or greater than the occurrences of the current integer. If not, return false as it isn't possible to divide the array into sets of k consecutive numbers. If everything passes through, return true.