All Subsequences After Deleting One Character
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.
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.