Missing Words in Subsequence

Given two strings, one is a subsequence if all of the elements of the first string occur in the same order within the second string. They do not have to be contiguous in the second string, but order must be maintained.

For example, given the string:

"I like cheese"

The words ('I', 'cheese') are one possible subsequence of that string. Words are space-delimited.

Given two strings s and t, where t is a subsequence of s, report the words of s that are missing in t (case-sensitive), in the order they are missing.

Example

s = 'I like cheese'
t = 'like'

Output:

['I', 'cheese']

Function Definition

def missingWords(s, t):
    s_words = s.split()
    t_words = t.split()
    missing = []
    t_ptr = 0

    for word in s_words:
        if t_ptr < len(t_words) and word == t_words[t_ptr]:
            t_ptr += 1
        else:
            missing.append(word)

    return missing

Explanation

• Split both input strings into word lists.
• Use a pointer t_ptr to track matching words in t.
• For each word in s_words, check:
  • If it matches the current word in t_words, advance the pointer.
  • Otherwise, it’s a missing word – append it to missing.
• Return the list missing in the order they appear.

---

An array of integers is almost sorted if at most one element can be deleted from it to make it perfectly sorted, ascending. For example, arrays [2, 1, 7], [13], [9, 2] and [1, 5, 6] are almost sorted because they have 0 or 1 elements out of place. The arrays [4, 2, 1], [1, 2, 6, 4, 3] are not because they have more than one element out of place. Given an array of n unique integers, determine the minimum number of elements to remove so it becomes almost sorted.

Example

arr = [3, 4, 2, 5, 1]

Remove 2 to get arr' = [3, 4, 5, 1] or remove 1 to get arr' = [3, 4, 2, 5], both of which are almost sorted. The minimum number of elements that must be removed in this case is 1.

Function Description

Complete the function minDeletions in the editor below.

minDeletions has the following parameter(s):

int arr[n]: an unsorted array of integers

Returns:

int: the minimum number of items that must be deleted to create an almost sorted array

Constraints

1 ≤ n ≤ 10^5  
1 ≤ arr[i] ≤ 10^9  
All elements of arr are distinct.

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.