Overview

This is a problem of determining whether each string contains sayounara as a subsequence. A subsequence is a string that can be formed by selecting characters from the original string in a non-contiguous manner (while preserving their order).

Analysis

What is Subsequence Checking?

Subsequence checking can be reduced to the question: “Can we find each character of the target string from left to right in the original string?”

For example, to check whether sayounara is contained as a subsequence in the string sxxxaxyzoounara:

1. Look for s → 1st character s matches ✓
2. Look for a → 5th character a matches ✓
3. Look for y → 7th character y matches ✓
4. Look for o → 9th character o matches ✓
5. … Continue similarly; if all characters up to the last a are found, output Yes

In this way, a greedy approach that scans the original string from left to right, searching for each character of the target string one by one from the beginning, is optimal.

Why is the Greedy Approach Correct?

By matching each character of the target at the earliest possible position, we leave as much room as possible in the remaining string. This ensures that we never miss a matching opportunity.

Comparison with a Naive Approach

When hearing “subsequence,” you might be tempted to enumerate all possible ways to select characters, but that would result in exponential time complexity and cause TLE. With the greedy approach described above, we can determine the answer by scanning the original string just once.

Algorithm

For each string \(S_i\), perform the following steps:

1. Initialize the pointer \(j\) for the target target = "sayounara" to \(0\).
2. Examine each character \(c\) of \(S_i\) from left to right.
   • If \(c\) matches target[j], increment \(j\) by \(1\).
   • If \(j\) reaches the length of target (\(9\)), the target is contained as a subsequence, so output Yes.
3. If \(j\) has not reached \(9\) after examining all of \(S_i\), output No.

Complexity

• Time complexity: \(O\left(\displaystyle\sum_{i=1}^{N} |S_i|\right)\)
  • Since we only scan each string once, the time is proportional to the total length of all strings. By the constraints, the total is at most \(5 \times 10^6\), which is sufficiently fast.
• Space complexity: \(O\left(\max |S_i|\right)\)
  • Space is needed to read each string. Including the output buffer, it is \(O(N + \max |S_i|)\).

Implementation Notes

• Fast input: Since the total length of strings can be up to \(5 \times 10^6\), which is large, in Python we use sys.stdin.readline to speed up input. Using the standard input() may result in TLE.

• Batch output: Instead of calling print each time, we accumulate results in a list and output them all at once with '\n'.join(out), reducing I/O overhead.

• Using rstrip(): Since readline() includes a trailing newline character, we remove it with .rstrip() before performing the check. Forgetting this may cause the newline character to interfere with the matching process.

• Early termination: As soon as all characters of the target string have been matched (\(j = 9\)), we immediately return True and skip scanning the rest of the string.

  Source Code

import sys
input = sys.stdin.readline

def check(s):
    target = "sayounara"
    j = 0
    for c in s:
        if c == target[j]:
            j += 1
            if j == len(target):
                return True
    return False

N = int(input())
out = []
for _ in range(N):
    s = input().rstrip()
    out.append("Yes" if check(s) else "No")
print('\n'.join(out))

---

This editorial was generated by claude4.6opus-thinking.