Minimum Times to Append String to Form Subsequence

Problem Statement

Given two strings source and target, find the minimum number of copies of source that must be concatenated such that target appears as a subsequence of the concatenation. Return -1 if it is impossible (i.e., target contains a character not in source).

A subsequence is obtained by deleting zero or more characters without changing order.

Example 1:

Input: source = "abc", target = "abcbc"
Output: 2
Explanation: "abc" + "abc" = "abcabc" contains "abcbc" as a subsequence
  (a_b_c_b_c from positions 0,1,2,4,5).

Example 2:

Input: source = "abc", target = "adbc"
Output: -1
Explanation: 'd' never appears in source.

Constraints:

• 1 <= source.length, target.length <= 10^5
• Both strings are lowercase English letters.

Difficulty: Medium

---

Pattern Recognition

• What is the structure of the input? Two strings; we need subsequence matching against concatenated copies.
• What are we optimizing? Minimum number of concatenations.
• What pattern does this suggest? Greedy walk through target with a precomputed "next occurrence" table for source. Each jump within a source copy is O(1); when we fall off the end, we wrap to the next copy.
• Why does this pattern fit? A subsequence match is greedy-consumable — always grab the earliest possible match. The "next occurrence" table turns each character lookup into O(1).

---

Approach

Brute Force — Two Pointers

Walk both strings. When target[j] == source[i], advance both; else advance i. Whenever i exits source, wrap to 0 and increment the copy counter.

Time: O(|source| * copies) — could be up to O(|source| * |target|) in the worst case. Space: O(1). Why insufficient: With source = "a" and target very long, this drags.

Optimal — Next-Occurrence Table

Key Insight: For each position i in source and each character c, precompute the smallest index >= i where c occurs in source. Then each character of target is handled in O(1) with a clean wrap-around.

Step-by-step:

1. Build nextPos[i][c] for i = 0..n and c = 0..25. nextPos[n][c] = -1; fill backward: nextPos[i][c] = nextPos[i+1][c], then overwrite the slot for source[i].
2. Check every character of target appears in source at all (nextPos[0][c] != -1). If any fails, return -1.
3. Walk target. Keep idx = 0 (current position in current source copy) and copies = 1.
4. For each char c in target:
   • If idx < n and nextPos[idx][c] != -1: advance idx = nextPos[idx][c] + 1.
   • Else: increment copies, set idx = nextPos[0][c] + 1.
5. Return copies.

Time: O(|source| * 26 + |target|). Space: O(|source| * 26).

---

Walkthrough

source = "abc", target = "abcbc".

Build nextPos (indexed as nextPos[i][char], showing relevant chars only):

i	a	b	c
3	-1	-1	-1
2	-1	-1	2
1	-1	1	2
0	0	1	2

Walk target:

target char	idx before	Decision	idx after	copies
a	0	nextPos[0][a]=0; idx = 1	1	1
b	1	nextPos[1][b]=1; idx = 2	2	1
c	2	nextPos[2][c]=2; idx = 3	3	1
b	3	idx == n; wrap: copies++, idx = nextPos[0][b] + 1 = 2	2	2
c	2	nextPos[2][c]=2; idx = 3	3	2

Answer: 2.

---

Implementation

TypeScript

function minAppendsForSubsequence(source: string, target: string): number {
  const n = source.length;
  // nextPos[i][c] = next index >= i in source with char c
  const nextPos: number[][] = Array.from({ length: n + 1 }, () => new Array(26).fill(-1));
  for (let i = n - 1; i >= 0; i--) {
    for (let c = 0; c < 26; c++) nextPos[i][c] = nextPos[i + 1][c];
    nextPos[i][source.charCodeAt(i) - 97] = i;
  }
  const hasChar = (c: number) => nextPos[0][c] !== -1;

  let copies = 1, idx = 0;
  for (const ch of target) {
    const c = ch.charCodeAt(0) - 97;
    if (!hasChar(c)) return -1;
    if (idx < n && nextPos[idx][c] !== -1) {
      idx = nextPos[idx][c] + 1;
    } else {
      copies++;
      idx = nextPos[0][c] + 1;
    }
  }
  return copies;
}

C++

class Solution {
public:
    int minAppendsForSubsequence(string source, string target) {
        int n = source.size();
        vector<array<int, 26>> nextPos(n + 1);
        for (int c = 0; c < 26; ++c) nextPos[n][c] = -1;
        for (int i = n - 1; i >= 0; --i) {
            nextPos[i] = nextPos[i + 1];
            nextPos[i][source[i] - 'a'] = i;
        }
        auto hasChar = [&](int c) { return nextPos[0][c] != -1; };

        int copies = 1, idx = 0;
        for (char ch : target) {
            int c = ch - 'a';
            if (!hasChar(c)) return -1;
            if (idx < n && nextPos[idx][c] != -1) {
                idx = nextPos[idx][c] + 1;
            } else {
                copies++;
                idx = nextPos[0][c] + 1;
            }
        }
        return copies;
    }
};

Watch out: Returning -1 on characters absent from source. Catch it with an early check — otherwise you loop forever wrapping.

Watch out: Off-by-one when advancing idx. You want idx = nextPos[...] + 1 so the next iteration looks strictly past the matched character.

Watch out: Initial copies = 1. You always start with one copy of source, even if target is empty (in which case 1 is still fine — the empty subsequence matches anywhere).

---

Complexity Analysis

	Time	Space
Brute Force Two-Pointer	O(	source
Precompute nextPos	O(	source

Bottleneck: Precomputing nextPos is O(|source| * 26); target walk is O(|target|). Alphabet size is the constant 26.

---

Edge Cases

1. Target contains char absent from source — Return -1.
2. Target is empty — Return 1 (one copy of source trivially contains the empty subsequence).
3. Target is a subsequence of a single source copy — Return 1.
4. source has length 1 — Count of matching copies equals number of target chars equal to that source char; -1 if mismatched.
5. source and target equal — Return 1.

---

Related Problems

• LC 392 — Is Subsequence: Simpler check without repetition.
• LC 1055 — Shortest Way to Form String: Exactly this problem (LeetCode Premium).
• LC 524 — Longest Word in Dictionary through Deleting: Subsequence check across many candidates.
• LC 727 — Minimum Window Subsequence: Finds minimum window in source containing target as subsequence.

---

What Is Expected at Each Level?

Junior / New Grad: Reach the two-pointer O(|source| * copies) solution. Identify the -1 failure case.

Mid-level: Propose the nextPos table and write it correctly. Explain why it's a speedup over the naive two-pointer walk.

Senior: Discuss binary-search-by-character as an alternative (store per-character sorted index lists, binary search for next occurrence >= idx) and compare memory trade-offs. Extend to multiple sources, rotated concatenations, and the case where target must be a substring (mention KMP / Aho-Corasick).