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 a boolean value indicating whether the subsequence exists in the string. For example, given the string "abcde" and the subsequence "ace", the output should be true.

Codemia · Accepted Answer

To determine if a given subsequence exists within a string, we can recognize that this problem can be effectively solved using the **two pointers technique**. The reason is that we need to check each character of the subsequence against the characters of the main string in order, while allowing for non-consecutive matches. By maintaining one pointer for the main string and another for the subsequence, we can traverse through the string and check for matches in a linear manner.

1. Initialize two pointers: `i` for the string and `j` for the subsequence, both starting at 0.
2. Iterate through the main string with the pointer `i`. For each character in the main string:
   - If the character at the current index `i` matches the character at index `j` of the subsequence, increment the `j` pointer.
   - Regardless of whether there was a match or not, always increment the `i` pointer to check the next character of the main string.
3. If the `j` pointer reaches the length of the subsequence, it means we have found a match for every character in the subsequence in order, and we return `True`. If we reach the end of the main string and `j` has not reached the end of the subsequence, we return `False`.

**Example:** For the string "abcde" and subsequence "ace":
- Start with `i=0`, `j=0`. `s[i]` = 'a', `sub[j]` = 'a' (match, increment `j` to 1)
- `i=1`, `s[i]` = 'b', `sub[j]` = 'c' (no match, increment `i`)
- `i=2`, `s[i]` = 'c', `sub[j]` = 'c' (match, increment `j` to 2)
- `i=3`, `s[i]` = 'd', `sub[j]` = 'e' (no match, increment `i`)
- `i=4`, `s[i]` = 'e', `sub[j]` = 'e' (match, increment `j` to 3)
- `j` equals length of subsequence, return `True`.

Here’s the Python implementation of the above approach:
```python
def is_subsequence(s: str, sub: str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(sub):
        if s[i] == sub[j]:
            j += 1
        i += 1
    return j == len(sub)
```
This function iterates through the main string and checks for matches with characters of the subsequence.

The time complexity of this solution is **O(n)**, where `n` is the length of the main string. This is because we traverse the string exactly once. The space complexity is **O(1)** since we are using a constant amount of extra space for the pointers. This makes the solution efficient and optimal given the constraints of the problem.

1. **Empty subsequence**: If the subsequence is empty, return `True` since an empty sequence is trivially a subsequence of any string.
2. **Empty string**: If the main string is empty and the subsequence is not, return `False`.
3. **Identical string and subsequence**: If the main string and subsequence are the same, return `True`.
4. **Non-matching characters**: If the characters in the subsequence are not present in the string in order, return `False`.
5. **Long subsequence**: If the subsequence is longer than the string, return `False` immediately.

Detect subsequence in string

Apple

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

Apple Machine Learning 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