Reverse Prefix of Word

🏠 ⬅️ ➡️

Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.

  • For example, if word = "abcdefd " and ch = "d ", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd ".

Return the resulting string.

Example 1:

Input: word = "abcdefd ", ch = "d " Output: "dcbaefd " Explanation: The first occurrence of "d " is at index 3. Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd ".

Example 2:

Input: word = "xyxzxe ", ch = "z " Output: "zxyxxe " Explanation: The first and only occurrence of "z " is at index 3. Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe ".

Example 3:

Input: word = "abcd ", ch = "z " Output: "abcd " Explanation: "z " does not exist in word. You should not do any reverse operation, the resulting string is "abcd ".

Constraints:

  • 1 <= word.length <= 250
  • word consists of lowercase English letters.
  • ch is a lowercase English letter.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, n
    character(len=250) :: word
    character :: ch

    ! read input
    read(*,*) word
    read(*,*) ch

    ! find first occurrence of ch
    n = len_trim(word)
    do i = 0, n - 1
        if (word(i:i+1) == ch) exit
    end do

    ! reverse segment
    if (i /= 0) then
        do j = 0, i - 1
            word(j:j+1) = word(i-j:i-j+1)
        end do
    end if

    ! print result
    write(*,'(a)') trim(word)

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

      integer :: i, j, n
      character(len=250) :: word, ch

      ! Read input
      read(*,*) word
      read(*,*) ch

      ! Find first occurrence of ch
      n = len_trim(word)
      do i = 1, n
          if (word(i:i) == ch) then
              exit
          end if
      end do

      ! Reverse segment
      if (i > 1) then
          do j = 1, (i-1)/2
              word(j:j) = word(i-j+1:i-j+1)
              word(i-j+1:i-j+1) = word(j:j)
          end do
      end if

      ! Print output
      write(*,*) word

      end program reverse_segment
🌐 Data from online sources 
import math
def minimum_speed(n, hour, dist):
    if n > math.ceil(hour): return -1
    low, high = 1, int(1e7)

    while low <= high:
        mid = low + (high - low) // 2
        time = sum(math.ceil(d / mid) for d in dist)
        if time <= hour:
            speed = mid
            high = mid - 1
        else:
            low = mid + 1

    return speed

The algorithm uses a binary search approach to find the minimum positive integer speed required for all trains to be on time. At first, we check if it's impossible to reach on time by counting if the number of distinct integer hours is less than the number of trains, if so we return -1. Then, we initialize the search space to be from 1 to (10^7). Within this search space, we calculate the sum of the time for each set of speeds from the middle of the search space. If this total time is less than or equal to the given hour, we choose the middle speed and reduce the search space to the left (since we are looking for the minimum speed). If the time is greater than the given hour, we increase the search space to the right. The process continues in this manner until we find the minimum speed required for the trains.

🌐 Data from online sources 
#include <cmath>
#include <vector>
int minimumSpeed(int n, float hour, std::vector<int>& dist) {
    if (n > ceil(hour)) return -1;
    int low = 1, high = 1e7, mid, speed;

    while (low <= high) {
        mid = low + (high - low) / 2;
        float time = 0;
        for (int i = 0; i < n; ++i) {
            time += ceil(dist[i] * 1.0 / mid);
        }
        if (time <= hour) {
            speed = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return speed;
}

The algorithm uses a binary search approach to find the minimum positive integer speed required for all trains to be on time. At first, we check if it's impossible to reach on time by counting if the number of distinct integer hours is less than the number of trains, if so we return -1. Then, we initialize the search space to be from 1 to (10^7). Within this search space, we calculate the sum of the time for each set of speeds from the middle of the search space. If this total time is less than or equal to the given hour, we choose the middle speed and reduce the search space to the left (since we are looking for the minimum speed). If the time is greater than the given hour, we increase the search space to the right. The process continues in this manner until we find the minimum speed required for the trains.