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: true if the subsequence exists in the string, and false otherwise.

Codemia · Accepted Answer

The problem requires us to determine if a given subsequence exists in a string while maintaining the order of characters. This is a classic problem that can be solved using a two-pointer technique. The reason this pattern applies here is that we can use one pointer to traverse the main string and another pointer to traverse the subsequence. By doing so, we can efficiently check if all characters of the subsequence appear in the main string in the correct order.

1. Initialize two pointers: `i` for the main string and `j` for the subsequence, both starting at 0.
2. Iterate over the main string with the pointer `i`:
   - If the character at `mainString[i]` matches `subsequence[j]`, increment `j` to check for the next character in the subsequence.
   - Regardless of a match, increment `i` to continue checking the next character in the main string.
3. If `j` reaches the length of the subsequence, it means we have found all characters in the correct order, and we can return `true`.
4. If the loop ends and `j` has not reached the end of the subsequence, return `false`.

**Example:** For mainString = "abcde" and subsequence = "ace", the pointers will move as follows:
- `i=0`, `j=0`: match 'a', increment `j` to 1.
- `i=1`, `j=1`: no match, move to next character.
- `i=2`, `j=1`: match 'c', increment `j` to 2.
- `i=3`, `j=2`: no match, move to next character.
- `i=4`, `j=2`: match 'e', increment `j` to 3 (end of subsequence).
Thus, return `true`.

```python
def is_subsequence(main_string: str, subsequence: str) -> bool:
    i, j = 0, 0
    while i < len(main_string) and j < len(subsequence):
        if main_string[i] == subsequence[j]:
            j += 1
        i += 1
    return j == len(subsequence)
```

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

1. If the main string is empty and the subsequence is also empty, return `true` (an empty string is a valid subsequence).
2. If the main string is empty but the subsequence is not, return `false` (a non-empty subsequence cannot be found).
3. If the subsequence is empty, return `true` (an empty subsequence can always be found).
4. If the subsequence is longer than the main string, return `false` (it is impossible to find a longer subsequence in a shorter string).

Detect subsequence in string

HRT

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

HRT 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