Increasing Decreasing String

🏠 ⬅️ ➡️

You are given a string s. Reorder the string using the following algorithm:

  1. Pick the smallest character from s and append it to the result.
  2. Pick the smallest character from s which is greater than the last appended character to the result and append it.
  3. Repeat step 2 until you cannot pick more characters.
  4. Pick the largest character from s and append it to the result.
  5. Pick the largest character from s which is smaller than the last appended character to the result and append it.
  6. Repeat step 5 until you cannot pick more characters.
  7. Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

Input: s = "aaaabbbbcccc " Output: "abccbaabccba " Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc " After steps 4, 5 and 6 of the first iteration, result = "abccba " First iteration is done. Now s = "aabbcc " and we go back to step 1 After steps 1, 2 and 3 of the second iteration, result = "abccbaabc " After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba "

Example 2:

Input: s = "rat " Output: "art " Explanation: The word "rat " becomes "art " after re-ordering it with the mentioned algorithm.

Constraints:

  • 1 <= s.length <= 500
  • s consists of only lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=:), allocatable :: s
    character(len=:), allocatable :: result

    ! Example 1
    s = 'aaaabbbbcccc'
    write(*,'(A)') solve(s)

    ! Example 2
    s = 'rat'
    write(*,'(A)') solve(s)

contains

    function solve(s) result(result)
        implicit none
        character(len=*), intent(in) :: s
        integer :: i, j, k
        character :: c
        logical :: found

        allocate(character(len=len(s)) :: result)
        result = ''

        do while (len(s) > 0)
            ! Step 1
            c = minval(s)
            call remove(s, c)
            result = trim(result) // c

            ! Step 2
            do while (len(s) > 0)
                c = minval(s, key=gt_char)
                if (c == '') exit
                call remove(s, c)
                result = trim(result) // c
            end do

            ! Step 3
            do while (len(s) > 0)
                c = minval(s)
                if (c == '') exit
                call remove(s, c)
                result = trim(result) // c
            end do

            ! Step 4
            c = maxval(s)
            call remove(s, c)
            result = trim(result) // c

            ! Step 5
            do while (len(s) > 0)
                c = maxval(s, key=lt_char)
                if (c == '') exit
                call remove(s, c)
                result = trim(result) // c
            end do

            ! Step 6
            do while (len(s) > 0)
                c = maxval(s)
                if (c == '') exit
                call remove(s, c)
                result = trim(result) // c
            end do
        end do

    contains

        pure function gt_char(c1, c2) result(gt)
            implicit none
            character, intent(in) :: c1, c2
            logical :: gt

            gt = ichar(c1) > ichar(c2)
        end function gt_char

        pure function lt_char(c1, c2) result(lt)
            implicit none
            character, intent(in) :: c1, c2
            logical :: lt

            lt = ichar(c1) < ichar(c2)
        end function lt_char

        subroutine remove(string, char)
            implicit none
            character(len=*), intent(inout) :: string
            character, intent(in) :: char
            integer :: i

            do while (index(string, char) /= 0)
                i = index(string, char)
                string(i:) = string(i+1:)
            end do
        end subroutine remove

    end function solve

end program main
✅ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: i, j, k, l, m, n, o
character(len=500) :: s, result

! Read input
read(*,*) s

! Initialize variables
i = 1
j = 1
k = 1
l = 1
m = 1
n = 1
o = 1

! Initialize result
result = ""

! Loop until all characters are used
do while (i <= len(s))

! Find smallest character
do while (j <= len(s))
if (s(j:j) < s(i:i)) then
i = j
endif
j = j + 1
enddo

! Append smallest character
result = result // s(i:i)

! Find smallest character greater than last appended character
do while (k <= len(s))
if (s(k:k) > s(i:i) .and. s(k:k) < s(o:o)) then
o = k
endif
k = k + 1
enddo

! Append smallest character greater than last appended character
result = result // s(o:o)

! Find largest character
do while (l <= len(s))
if (s(l:l) > s(i:i)) then
i = l
endif
l = l + 1
enddo

! Append largest character
result = result // s(i:i)

! Find largest character smaller than last appended character
do while (m <= len(s))
if (s(m:m) < s(i:i) .and. s(m:m) > s(n:n)) then
n = m
endif
m = m + 1
enddo

! Append largest character smaller than last appended character
result = result // s(n:n)

! Increment variables
i = i + 1
j = j + 1
k = k + 1
l = l + 1
m = m + 1
n = n + 1
o = o + 1

! End loop
enddo

! Print result
print *, result

end
🌐 Data from online sources 
def numberOfSubarrays(nums, k):
    n = len(nums)
    result = count = 0
    odd_count = [0] * (n + 1)

    odd_count[0] = 1
    for num in nums:
        count += num % 2
        if count >= k:
            result += odd_count[count - k]
        odd_count[count] += 1

    return result
  1. Initialize array oddCount with a size of n+1 and set oddCount[0] to 1.
  2. Initialize count and result to 0.
  3. Iterate through the input array nums.
  4. For each element, increment count by the value of the element modulo 2 (if the element is odd, it increments by 1, otherwise by 0).
  5. If count is greater than or equal to k, increment result by the value of oddCount[count - k].
  6. Increment oddCount[count].
  7. After iteration, return result as the number of nice sub-arrays.

This algorithm works by tracking the number of odd elements within a subarray and storing the cumulative sums in the oddCount array. By iterating through the input array and incrementing the count, the algorithm determines whether a subarray is nice by checking if the count is greater than or equal to k and updating the result accordingly.

🌐 Data from online sources 
int numberOfSubarrays(vector<int>& nums, int k) {
    int n = nums.size(), result = 0, count = 0;
    vector<int> oddCount(n + 1, 0);

    oddCount[0] = 1;
    for (int i = 0; i < n; i++) {
        count += nums[i] % 2;
        if (count >= k) result += oddCount[count - k];
        oddCount[count]++;
    }

    return result;
}
  1. Initialize array oddCount with a size of n+1 and set oddCount[0] to 1.
  2. Initialize count and result to 0.
  3. Iterate through the input array nums.
  4. For each element, increment count by the value of the element modulo 2 (if the element is odd, it increments by 1, otherwise by 0).
  5. If count is greater than or equal to k, increment result by the value of oddCount[count - k].
  6. Increment oddCount[count].
  7. After iteration, return result as the number of nice sub-arrays.

This algorithm works by tracking the number of odd elements within a subarray and storing the cumulative sums in the oddCount array. By iterating through the input array and incrementing the count, the algorithm determines whether a subarray is nice by checking if the count is greater than or equal to k and updating the result accordingly.