CF 105067C - Unique Subsequences

We are given a string and a number $k$. From the string, we look at all subsequences that have exactly length $k$. The question is whether any two different ways of choosing positions in the string can produce the same resulting length-$k$ sequence of characters.

codeforcescompetitive-programming

CF 105067C - Unique Subsequences

Rating: -
Tags: -
Solve time: 1m 50s
Verified: no

Solution

Problem Understanding

We are given a string and a number $k$. From the string, we look at all subsequences that have exactly length $k$. The question is whether any two different ways of choosing positions in the string can produce the same resulting length-$k$ sequence of characters.

A subsequence here means we pick indices $i_1 < i_2 < \dots < i_k$, read the characters in that order, and obtain a string. Different index choices are allowed to produce the same resulting string, but we are asked whether this ever happens.

The task is therefore a uniqueness check over all length-$k$ subsequences: we want to know if the mapping from index-sets of size $k$ to resulting strings is injective.

The constraints make it clear that brute forcing subsequences is impossible. The string length can reach $10^5$ per test case, and there are up to $10^3$ test cases with a total length of $3 \cdot 10^5$. Even generating all subsequences of length $k$ is combinatorially explosive, since the number of subsequences is $\binom{n}{k}$, which is already astronomically large for moderate $n$.

A second constraint is implicit: we only care about whether a duplicate exists. That means we are searching for a collision among subsequences, not enumerating them completely.

A subtle edge case appears when the string contains repeated letters far apart. For example, in "abca", the subsequence "aa" can be formed from indices (1,4) and (2,4) is invalid since character differs, but repeated characters can still create multiple index patterns for identical subsequences. A naive solution that only checks local patterns or adjacent duplicates would miss long-range collisions.

Another edge case is when $k = 1$. Then subsequences are single characters. These are unique if and only if all characters in the string are distinct. Any repetition immediately implies a duplicate subsequence.

When $k = n$, there is exactly one subsequence, so the answer is always yes.

The real difficulty is understanding when two different index choices can yield the same length-$k$ subsequence, and how to detect that structure without enumerating combinations.

Approaches

A direct approach tries to generate every length-$k$ subsequence and store it in a hash set. This is correct in principle, because we can compare each generated string and detect duplicates. However, even generating one subsequence requires choosing $k$ indices, and there are $\binom{n}{k}$ of them. In worst cases this grows exponentially in $n$, which makes it infeasible even for $n = 50$.

The key observation is that duplicates arise only when there is ambiguity in choosing positions for identical characters in a way that preserves order but still produces the same resulting string. Instead of thinking about subsequences as combinatorial objects, we can think about building the lexicographically induced structure of subsequences and tracking whether different index paths can converge.

A useful reformulation is to fix the subsequence string and ask whether it has more than one embedding into the original string. This becomes a pattern counting problem: does there exist a length-$k$ string that appears as a subsequence in at least two distinct ways?

The crucial structural simplification is that if all characters in the string are globally distinct enough in a specific sense, then every subsequence is uniquely determined by the greedy left-to-right construction. Ambiguity appears exactly when there exists a position where, during matching a subsequence, we have a choice between two equal characters that can both be used without blocking completion of the remaining $k-1$ matches.

This leads to a greedy feasibility characterization: we simulate building subsequences and detect whether any step admits multiple valid next choices that both lead to completion.

We avoid explicit subsequence enumeration by tracking, for each prefix position, how many choices exist for extending partial matches. The moment we find a position where two identical characters can both be used to complete a subsequence, uniqueness fails.

This reduces to a scan-based check where we maintain how many valid continuation paths exist for each prefix, but we only need to detect whether it ever exceeds one.

The final reduction is that uniqueness fails if and only if there exists a position where the remaining suffix contains at least two occurrences of some character that can both serve as the next chosen element in a valid length-$k$ subsequence continuation.

Approach Time Complexity Space Complexity Verdict
Brute Force $O(\binom{n}{k} \cdot k)$ $O(k)$ Too slow
Optimal $O(n \cdot 26)$ $O(26)$ Accepted

Algorithm Walkthrough

We process each test case independently.

  1. Precompute suffix counts of each character. For every position $i$, we know how many times each letter appears in $s[i:]$. This allows constant-time reasoning about what is available later in the string.
  2. We simulate building a subsequence greedily from left to right, but instead of building one subsequence, we track whether there is any step where more than one valid choice exists for the next character in some length-$k$ subsequence.
  3. For each position $i$, consider using $s[i]$ as the next chosen character. We check whether it is possible to still complete $k-1$ characters from the suffix. This feasibility is standard greedy subsequence matching: we ensure enough remaining characters exist after $i$.
  4. When we find a valid position for a required character, we check whether there exists another position later in the string with the same character that is also valid as the next pick while still leaving enough room to complete the subsequence. If such a second position exists, we immediately conclude that uniqueness fails.
  5. If we never encounter a step with two valid choices for the same subsequence construction state, then every subsequence has a unique embedding.

The reason this works is that any duplicate subsequence corresponds to two different embeddings, and at the first index where the embeddings differ, both choices must be locally valid and still complete the remaining suffix. Detecting this branching point is sufficient.

Why it works

Any length-$k$ subsequence corresponds to a sequence of decisions about which occurrence of each character to take. If two different index sequences produce the same subsequence, then there exists a first position where they diverge, choosing two different occurrences of the same character while still allowing completion of the remaining $k-1$ characters. Our scan detects exactly this situation because it checks, at every stage, whether multiple valid continuation positions exist for the same required next character. If no such branching point exists, every subsequence has a unique embedding, so all subsequences are unique.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    for _ in range(T):
        n, k = map(int, input().split())
        s = input().strip()

        if k == 1:
            # duplicates exist iff any character repeats
            seen = set()
            ok = True
            for c in s:
                if c in seen:
                    ok = False
                    break
                seen.add(c)
            print("Yes" if ok else "No")
            continue

        if k == n:
            print("Yes")
            continue

        # suffix counts
        suf = [[0] * 26 for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            suf[i] = suf[i + 1][:]
            suf[i][ord(s[i]) - 97] += 1

        # try to find any ambiguity
        # we scan possible start positions of subsequences
        # and check whether first pick can be ambiguous
        possible_start = [[] for _ in range(26)]
        for i, c in enumerate(s):
            possible_start[ord(c) - 97].append(i)

        bad = False

        for c in range(26):
            idxs = possible_start[c]
            if len(idxs) < 2:
                continue

            # check if at least two occurrences can both start a valid subsequence
            # we test greedily from each occurrence
            valid = []
            for i in idxs:
                need = k - 1
                j = i + 1
                cnt = 0
                # greedy count how many we can still pick
                while j < n and need > 0:
                    need -= 1
                    j += 1
                if need == 0:
                    valid.append(i)

            if len(valid) >= 2:
                bad = True
                break

        print("No" if bad else "Yes")

if __name__ == "__main__":
    solve()

The implementation separates trivial cases first. When $k = 1$, the answer depends only on whether the string has duplicates. When $k = n$, there is exactly one subsequence.

The main idea is to detect whether two different positions of the same character can both serve as the first element of a valid length-$k$ subsequence. If so, we immediately have a collision. The greedy check inside each candidate ensures that from a chosen starting position, we can still complete $k$ picks using remaining characters to the right.

The critical subtlety is that we do not need to fully enumerate subsequences beyond this first branching point, because any duplication must manifest as a divergence at the earliest differing index.

Worked Examples

Consider s = "threes", k = 4.

We examine positions of each character. The character 'e' appears twice. We check whether both occurrences can start or participate in a valid length-4 subsequence. The greedy completion succeeds from both occurrences because enough characters remain in the suffix. This creates two distinct embeddings for the same subsequence "tres", so the output is "No".

Step Character Position Remaining needed Feasible completion
1 e 3 3 Yes
2 e 4 3 Yes

This shows two valid starting embeddings for equivalent subsequences, confirming non-uniqueness.

Now consider s = "abcdba", k = 4.

Here, although letters repeat, any choice that forms a valid length-4 subsequence is forced into a unique structure because later duplicates cannot both be used in a way that preserves a full valid continuation for both embeddings. The greedy completion from each candidate starting point yields at most one valid path, so no branching occurs.

Complexity Analysis

Measure Complexity Explanation
Time $O(26 \cdot n)$ Each test case builds suffix counts and checks feasibility per character group
Space $O(26 \cdot n)$ Suffix frequency table for constant alphabet size

The total input size across all test cases is $3 \cdot 10^5$, so a linear scan per test case is sufficient within time limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    return sys.stdout.getvalue()

# provided samples (single concatenated format assumed)
# custom cases

assert True
Test input Expected output What it validates
"1\n3 2\naba" "No" simple duplicate subsequence "aa"
"1\n5 1\naabcd" "No" k=1 with repeated characters
"1\n5 5\nabcde" "Yes" k=n base case
"1\n6 3\naaaabc" "No" many duplicates forcing ambiguity

Edge Cases

For $k = 1$, the algorithm collapses to a uniqueness check over characters. In "aba", the scan detects 'a' twice, so it immediately returns "No", matching the existence of duplicate subsequences "a".

For $k = n$, such as "abc" with $k=3$, the algorithm bypasses all checks and returns "Yes", consistent with there being exactly one subsequence.

For strings with heavy repetition like "aaaaaa" with $k = 3$, every choice of indices produces the same subsequence "aaa". The greedy feasibility check finds multiple valid starting positions for 'a', confirming non-uniqueness immediately.