Sorting the Sentence

🏠 ⬅️ ➡️

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters.

A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence.

  • For example, the sentence "This is a sentence " can be shuffled as "sentence4 a3 is2 This1 " or "is2 sentence4 This1 a3 ".

Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.

Example 1:

Input: s = "is2 sentence4 This1 a3 " Output: "This is a sentence " Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4 ", then remove the numbers.

Example 2:

Input: s = "Myself2 Me1 I4 and3 " Output: "Me Myself and I " Explanation: Sort the words in s to their original positions "Me1 Myself2 and3 I4 ", then remove the numbers.

Constraints:

  • 2 <= s.length <= 200
  • s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.
  • The number of words in s is between 1 and 9.
  • The words in s are separated by a single space.
  • s contains no leading or trailing spaces.

1. All characters in a are strictly less than those in b (i.e., a[i] < b[i] for all i). 2. All characters in b are strictly less than those in a (i.e., a[i] > b[i] for all i). 3. All characters in a and b are the same (i.e., a[i] = b[i] for all i).

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=:), allocatable :: sentence
    integer :: nwords
    character(len=:), allocatable :: shuffled_sentence
    character(len=:), allocatable :: unshuffled_sentence

    ! Example 1
    sentence = "This is a sentence "
    nwords = size(sentence)
    shuffled_sentence = "sentence4 a3 is2 This1 "
    call solve(sentence, nwords, shuffled_sentence, unshuffled_sentence)
    write (*,*) unshuffled_sentence

    ! Example 2
    sentence = "Myself2 Me1 I4 and3 "
    nwords = size(sentence)
    shuffled_sentence = "Myself2 Me1 I4 and3 "
    call solve(sentence, nwords, shuffled_sentence, unshuffled_sentence)
    write (*,*) unshuffled_sentence

contains

    subroutine solve(sentence, nwords, shuffled_sentence, unshuffled_sentence)
        implicit none
        character(len=*), intent(in) :: sentence
        integer, intent(in) :: nwords
        character(len=*), intent(in) :: shuffled_sentence
        character(len=*), intent(out) :: unshuffled_sentence

        integer :: i, j, k
        character(len=nwords) :: temp

        do i = 1, nwords
            read (shuffled_sentence(i:i+1), '(I1)') j
            k = index(sentence, ' ') + (j - 1) * len(sentence) / nwords
            temp(i:i) = sentence(k:k)
        end do
        unshuffled_sentence = trim(temp)
    end subroutine solve

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=200) :: sentence
character(len=200) :: shuffled_sentence
character(len=200) :: word

! Read input sentence
read(*,*) shuffled_sentence

! Initialize variables
i = 1
j = 1
k = 1
l = 1
m = 1
n = 1
o = 1
p = 1
q = 1
r = 1
s = 1
t = 1
u = 1
v = 1
w = 1
x = 1
y = 1
z = 1

! Loop through each character in the shuffled sentence
do while (i <= len(shuffled_sentence))
    ! Check if the current character is a digit
    if (shuffled_sentence(i:i) >= '0' .and. shuffled_sentence(i:i) <= '9') then
        ! Get the word position
        word = shuffled_sentence(j:k-1)
        j = k + 1
        k = k + len(word)

        ! Check if the word position is valid
        if (word >= '1' .and. word <= '9') then
            ! Get the word
            word = shuffled_sentence(l:m-1)
            l = m + 1
            m = m + len(word)

            ! Check if the word is valid
            if (word >= 'a' .and. word <= 'z') then
                ! Add the word to the sentence
                sentence(n:n+len(word)-1) = word
                n = n + len(word)
            end if
        end if
    else
        ! Add the current character to the sentence
        sentence(o:o) = shuffled_sentence(i:i)
        o = o + 1
    end if

    ! Increment variables
    i = i + 1
    j = j + 1
    k = k + 1
    l = l + 1
    m = m + 1
    n = n + 1
    o = o + 1
    p = p + 1
    q = q + 1
    r = r + 1
    s = s + 1
    t = t + 1
    u = u + 1
    v = v + 1
    w = w + 1
    x = x + 1
    y = y + 1
    z = z + 1
end do

! Print the reconstructed sentence
print *, sentence

end
🌐 Data from online sources 
def min_operations_to_satisfy_conditions(a: str, b: str) -> int:
    same, less, greater = 0, 0, 0

    for i in range(len(a)):
        if a[i] == b[i]:
            same += 1
        elif a[i] < b[i]:
            less += 1
        else:
            greater += 1

    return min(same + max(less, greater), less, greater)

The algorithm keeps track of three counts: 'same', 'less', and 'greater'. These counts store the number of characters that are the same, less, and greater in string a compared to string b, respectively. Iterate through the characters in a and b simultaneously, comparing each character and updating the counts accordingly. The minimum number of operations needed to satisfy one of the three conditions is then calculated as the minimum of the sum of 'same' and the maximum of 'less' and 'greater', as well as 'less' and 'greater' individually. This is because you can either change all 'same' characters and one of 'less' or 'greater', or change only one of 'less' or 'greater' while keeping the other characters in the same order.

The time complexity of the algorithm is O(n) where n is the length of input strings a and b, as it iterates through each character pair in the strings once.

🌐 Data from online sources 
int minOperationsToSatisfyConditions(std::string a, std::string b) {
    int same = 0, less = 0, greater = 0;

    for (size_t i = 0; i < a.length(); ++i) {
        if (a[i] == b[i]) same++;
        else if (a[i] < b[i]) less++;
        else greater++;
    }

    return std::min({same + std::max(less, greater), less, greater});
}

The algorithm keeps track of three counts: 'same', 'less', and 'greater'. These counts store the number of characters that are the same, less, and greater in string a compared to string b, respectively. Iterate through the characters in a and b simultaneously, comparing each character and updating the counts accordingly. The minimum number of operations needed to satisfy one of the three conditions is then calculated as the minimum of the sum of 'same' and the maximum of 'less' and 'greater', as well as 'less' and 'greater' individually. This is because you can either change all 'same' characters and one of 'less' or 'greater', or change only one of 'less' or 'greater' while keeping the other characters in the same order.

The time complexity of the algorithm is O(n) where n is the length of input strings a and b, as it iterates through each character pair in the strings once.