Shift Word to Back

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']
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
Previous
Prefix-Suffix Swap
a
0
g
1
j
o
2
o
3
d
4
r
5
e
6
a
7
d
8
i
9
n
10
g
11
Step 1 / 3
Step 1:
Found indices for 'od': {2, 4}.
Pointers: j=2
Focus: select @ [2, 4]