Check Whether a Word Repeated K Times Is a Subsequence

Question

The candidate is asked to determine if a string can be formed as a subsequence of another string after repeating it a specified number of times.

Codemia · Accepted Answer

To determine if `str2` repeated `k` times can be a subsequence of `str1`, we need to first understand the properties of subsequences. A subsequence allows for characters to be non-contiguous but must maintain the order. Thus, the main task is to check if we can find all characters of `str2` repeated `k` times within `str1` while respecting their order.

1. **Calculate the Target String**: Create a new string `target` by repeating `str2`, `k` times. 
2. **Two-Pointer Technique**: Use two pointers, one for `str1` and one for `target`. 
3. **Iterate Through Characters**: Move through `str1` and `target`, incrementing the pointer for `target` whenever a match is found in `str1`. 
4. **Check Completion**: If the pointer for `target` reaches the end of `target`, then `str2` repeated `k` times is a subsequence of `str1`.

The time complexity of this approach is O(n + m), where n is the length of `str1` and m is the length of `target`. The space complexity is O(m) due to the storage of the `target` string.

```python
def is_subsequence(str1: str, str2: str, k: int) -> bool:
    target = str2 * k
    i, j = 0, 0
    while i < len(str1) and j < len(target):
        if str1[i] == target[j]:
            j += 1
        i += 1
    return j == len(target)
```

Consider cases where `str2` is empty or `k` is 0; in such cases, the answer should be true as an empty string is a subsequence of any string. Also, if `str2` is longer than `str1`, it cannot be a subsequence, and we should return false immediately.

Check Whether a Word Repeated K Times Is a Subsequence

Quince

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Quince 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