Detect subsequence in string

Question

Given a string and a subsequence, determine if the subsequence can be found within the string in the same order, but not necessarily consecutively. The function should return true if the subsequence exists in the string, and false otherwise. For example, given the string "abcde" and the subsequence "ace", the output should be true.

Codemia · Accepted Answer

To determine if a subsequence exists within a given string, we can utilize the **two pointers** technique. This approach is suitable because we can sequentially traverse both the main string and the subsequence, advancing the pointers only when we find a match. This allows us to check for the order of characters in the subsequence without the need for additional data structures or complex algorithms.

1. Initialize two pointers: one (`s_index`) for the main string and one (`sub_index`) for the subsequence.
2. Traverse the main string using `s_index`. For each character in the string:
   - If the character at `s_index` matches the character at `sub_index`, increment `sub_index`.
   - Always increment `s_index` to continue traversing the main string.
3. If `sub_index` reaches the length of the subsequence by the end of the traversal, it means all characters of the subsequence have been found in order. Otherwise, it does not exist.

**Example:** For string `s = 'abcde'` and subsequence `sub = 'ace':`
- Start with `s_index = 0` and `sub_index = 0`.
- `s[0]` ('a') matches `sub[0]` ('a'), so increment both pointers.
- `s[1]` ('b') does not match `sub[1]` ('c'), only increment `s_index`.
- `s[2]` ('c') matches `sub[1]`, increment both.
- `s[3]` ('d') does not match `sub[2]` ('e'), increment `s_index`.
- `s[4]` ('e') matches `sub[2]`, increment both.
- At this point, `sub_index` equals the length of `sub`, thus return `true`.

Here's a Python implementation of the above approach:
```python
def is_subsequence(s: str, sub: str) -> bool:
    s_index, sub_index = 0, 0
    while s_index < len(s) and sub_index < len(sub):
        if s[s_index] == sub[sub_index]:
            sub_index += 1
        s_index += 1
    return sub_index == len(sub)
```
This function checks whether `sub` is a subsequence of `s` by iterating through both strings with the two-pointer technique.

The time complexity of this solution is **O(n)**, where `n` is the length of the main string `s`. This is because we traverse the string only once. The space complexity is **O(1)** since we are using a constant amount of space for the pointers, regardless of the input size.

1. **Empty String and Subsequence:** If both the string and subsequence are empty, return `true`.
2. **Empty Subsequence:** If the subsequence is empty (e.g., `''`), return `true` because an empty subsequence is always found.
3. **Empty String:** If the main string is empty but the subsequence is not (e.g., `s = ''`, `sub = 'a'`), return `false`.
4. **Single Character Matches:** If `s` has one character and `sub` also has one character, only return `true` if they are the same.

Detect subsequence in string

Snapchat

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Snapchat Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string