Minimum Moves to Convert String

🏠 ⬅️ ➡️

You are given a string s consisting of n characters which are either 'X' or 'O'.

A move is defined as selecting three consecutive characters of s and converting them to 'O'. Note that if a move is applied to the character 'O', it will stay the same.

Return the minimum number of moves required so that all the characters of s are converted to 'O'.

Example 1:

Input: s = "XXX " Output: 1 Explanation: XXX -> OOO We select all the 3 characters and convert them in one move.

Example 2:

Input: s = "XXOX " Output: 2 Explanation: XXOX -> OOOX -> OOOO We select the first 3 characters in the first move, and convert them to 'O'. Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3:

Input: s = "OOOO " Output: 0 Explanation: There are no 'X's in s to convert.

Constraints:

  • 3 <= s.length <= 1000
  • s[i] is either 'X' or 'O'.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

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

    read(*,*) n
    read(*,*) s

    do i = 1, n-2
        if (s(i:i+2) == 'XXX') then
            write(*,'(I0)') 1
            return
        end if
    end do

    do i = 1, n-2
        if (s(i:i+2) == 'XXO') then
            write(*,'(I0)') 2
            return
        end if
    end do

    do i = 1, n-2
        if (s(i:i+2) == 'XXOX') then
            write(*,'(I0)') 3
            return
        end if
    end do

    write(*,'(I0)') 4

end program main
✅ Compiled
❌ Executed
❌ Correct 
! This is a full Fortran script with a valid main entry point that solves the problem.

program min_moves

implicit none

! Declare the variables
integer :: n, i, j, k
character(len=1000) :: s
integer :: moves

! Read the input
read(*,*) n
read(*,*) s

! Initialize the variables
moves = 0

! Loop through the string and count the number of moves
do i = 1, n-2
    if (s(i:i+2) == 'XXX') then
        moves = moves + 1
    end if
end do

! Print the output
write(*,*) moves

end program min_moves
🌐 Data from online sources 
def maximumRemovals(s: str, p: str, removable: List[int]) -> int:
    low, high = 0, len(removable)
    while low < high:
        mid = low + (high - low + 1) // 2
        ss = list(s)
        for i in range(mid):
            ss[removable[i]] = '-'
        j, i = 0, 0
        while i < len(ss) and j < len(p):
            if ss[i] == p[j]:
                j += 1
            i += 1
        if j == len(p):
            low = mid
        else:
            high = mid - 1
    return low

The algorithm is basically binary search. We iterate through the removable array and start by removing `mid` (the middle element) number of characters from `s`. Then, we check if `p` is still a subsequence of the modified string. If it's a subsequence, it means we can try removing more characters, hence updating the lower bound `low` to `mid`. If it's not a subsequence, we update the upper bound `high` to `mid - 1`, meaning we have to try removing fewer characters. We do this until `low < high`, and then return the maximum value of `k = low` which will give us the maximum removable characters where `p` is still a subsequence of `s`.
🌐 Data from online sources 
int maximumRemovals(string s, string p, vector<int>& removable) {
    int low = 0, high = removable.size();
    while (low < high) {
        int mid = low + (high - low + 1) / 2;
        string ss = s;
        for (int i = 0; i < mid; ++i) {
            ss[removable[i]] = '-';
        }
        int j = 0, i = 0;
        while (i < ss.size() && j < p.size()) {
            if (ss[i] == p[j]) {
                ++j;
            }
            ++i;
        }
        if (j == p.size()) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

The algorithm is basically binary search. We iterate through the removable array and start by removing `mid` (the middle element) number of characters from `s`. Then, we check if `p` is still a subsequence of the modified string. If it's a subsequence, it means we can try removing more characters, hence updating the lower bound `low` to `mid`. If it's not a subsequence, we update the upper bound `high` to `mid - 1`, meaning we have to try removing fewer characters. We do this until `low < high`, and then return the maximum value of `k = low` which will give us the maximum removable characters where `p` is still a subsequence of `s`.