Shift Word to Back

01 · Question

You are given an array of letters, arr, and a string, word. We know that word appears within arr as a subsequence. Identify the earliest occurrence of word in arr and move all those letters, in order, to the end of arr. You must do this in place.

Example 1:

Input: arr = ['a', 'g', 'o', 'o', 'd', 'r', 'e', 'a', 'd', 'i', 'n', 'g'], word = "od"
Output: ['a', 'g', 'o', 'r', 'e', 'a', 'd', 'i', 'n', 'g', 'o', 'd']

02 · Solution

Reference solution

1def shiftWordToBack(arr: List[str], word: str) -> None:
2    # 1. Find indices of earliest subsequence
3    indices = set()
4    j = 0
5    for i, char in enumerate(arr):
6        if j < len(word) and char == word[j]:
7            indices.add(i)
8            j += 1
9            
10    # 2. Shift non-word characters to front
11    writer = 0
12    for seeker in range(len(arr)):
13        if seeker not in indices:
14            arr[writer] = arr[seeker]
15            writer += 1
16            
17    # 3. Append word at the end
18    for i, char in enumerate(word):
19        arr[writer + i] = char

Prefix-Suffix Swap