How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Two Sigma.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Two Sigma during technical interviews.

All Subsequences After Deleting One Character

Q: All Subsequences After Deleting One Character

This question evaluates string manipulation and combinatorial reasoning skills, specifically understanding of subsequence enumeration, duplicate elimination, lexicographic ordering, and algorithmic complexity.

Company: Two Sigma

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a string `s` of length `n` consisting of lowercase English letters. Consider every string that can be obtained by deleting **exactly one** character from `s` — there are `n` such strings, one for each deletion position. For each resulting string `t`, generate **every non-empty subsequence** of `t`. A subsequence of `t` is obtained by deleting zero or more characters from `t`; the remaining characters must keep the relative order they had in `t` (and therefore the relative order they had in the original string `s`). Collect all strings generated across all `n` deletion results, remove duplicates, and return them sorted in ascending lexicographic order. ### Example Input: `s = "acb"` Deleting one character from `"acb"` produces three strings: - Delete `'a'` → `"cb"`, whose non-empty subsequences are `"c"`, `"b"`, `"cb"` - Delete `'c'` → `"ab"`, whose non-empty subsequences are `"a"`, `"b"`, `"ab"` - Delete `'b'` → `"ac"`, whose non-empty subsequences are `"a"`, `"c"`, `"ac"` Note that the characters of each subsequence keep their original relative order: from `"cb"` the two-character subsequence is `"cb"`, not `"bc"`. Combining all of them, removing duplicates, and sorting lexicographically gives: Output: `["a", "ab", "ac", "b", "c", "cb"]` ### Constraints - `2 <= n <= 15` - `s` consists of lowercase English letters only; `s` may contain repeated characters. - The output must contain each distinct string exactly once, in ascending lexicographic order.

Quick Answer: This question evaluates string manipulation and combinatorial reasoning skills, specifically understanding of subsequence enumeration, duplicate elimination, lexicographic ordering, and algorithmic complexity.

You are given a string `s` of length `n` consisting of lowercase English letters. Consider every string that can be obtained by deleting **exactly one** character from `s` — there are `n` such strings, one for each deletion position. For each resulting string `t`, generate **every non-empty subsequence** of `t`. A subsequence of `t` keeps the relative order of the characters it retains (and therefore their original relative order in `s`). Collect all strings generated across all `n` deletion results, remove duplicates, and return them sorted in ascending lexicographic order. ### Example Input: `s = "acb"` - Delete `'a'` → `"cb"` → subsequences `"c"`, `"b"`, `"cb"` - Delete `'c'` → `"ab"` → subsequences `"a"`, `"b"`, `"ab"` - Delete `'b'` → `"ac"` → subsequences `"a"`, `"c"`, `"ac"` Subsequence characters keep their original order (from `"cb"` the two-character subsequence is `"cb"`, not `"bc"`). Combining, de-duplicating, and sorting gives `["a", "ab", "ac", "b", "c", "cb"]`. ### Constraints - `2 <= n <= 15` - `s` consists of lowercase English letters only; `s` may contain repeated characters. - The output must contain each distinct string exactly once, in ascending lexicographic order.

Constraints

2 <= n <= 15
s consists of lowercase English letters only
s may contain repeated characters
Output contains each distinct string exactly once, sorted ascending lexicographically

Examples

Input: ("acb",)

Expected Output: ["a", "ab", "ac", "b", "c", "cb"]

Explanation: The worked example: deletions cb/ab/ac contribute {c,b,cb}, {a,b,ab}, {a,c,ac}; union sorted is a, ab, ac, b, c, cb.

Input: ("abc",)

Expected Output: ["a", "ab", "ac", "b", "bc", "c"]

Explanation: Deletions give bc, ac, ab; union {b,c,bc,a,ac,ab} sorted is a, ab, ac, b, bc, c.

Input: ("ab",)

Expected Output: ["a", "b"]

Explanation: n=2 boundary: deleting one char leaves a single character each time, yielding {a, b}.

Input: ("aa",)

Expected Output: ["a"]

Explanation: Both deletions leave "a"; the only non-empty subsequence is "a", so the deduped result is a single element.

Input: ("aba",)

Expected Output: ["a", "aa", "ab", "b", "ba"]

Explanation: Deletions ba/aa/ab give {b,a,ba}, {a,aa}, {a,b,ab}; union sorted is a, aa, ab, b, ba, exercising cross-deletion dedup.

Hints

There are exactly n deletion results. For each, enumerate its non-empty subsequences with a bitmask over its (n-1) characters.
Use a set to absorb duplicates that arise both within a deletion result (from repeated letters) and across different deletion results.
Preserving relative order is automatic if you build each subsequence by scanning the deletion result left to right; just sort the final set lexicographically.

Quick Overview

This question evaluates string manipulation and combinatorial reasoning skills, specifically understanding of subsequence enumeration, duplicate elimination, lexicographic ordering, and algorithmic complexity.