Infinite String

Let $C$ be the set of characters that occur at least once in $T$.

Every character of a common subsequence must occur in $T^\infty$, so it must belong to $C$. Thus, the answer cannot exceed the number of characters of $S$ that belong to $C$.

Conversely, take every character of $S$ that belongs to $C$, preserving its order, and call the resulting string $X$. Each character of $X$ occurs somewhere in $T$. After any already selected position of $T^\infty$, the next copy of contains the desired character, so all characters of can be selected one by one. Therefore, is a subsequence of .

Hence, the answer is exactly the number of characters of $S$ that occur at least once in $T$.

The time complexity is $O(|S|+|T|)$ and the extra space complexity is $O(1)$.

Solution written by GPT5.6