Optimal Grid Path Protocol 7 — Problem Statement & Solution Guide

StringsMediumSubsequence Verification

TimeO(n+m)

SpaceO(1)

Problem Description

You are provided with two strings, source and target, representing a sequence of operational codes and a required verification pattern, respectively. The system requires determining whether target can be formed by deleting zero or more characters from source without reordering the remaining characters. This is a classic subsequence verification task where the relative order of characters in target must be preserved as they appear in source.

Your task is to implement a function that returns true if target is a subsequence of source, and false otherwise. The solution must efficiently handle large input sizes by leveraging a linear scan approach that tracks the current position in the target string while iterating through the source string. This ensures optimal time complexity suitable for high-throughput data processing environments.

The input consists of two strings composed of lowercase English letters. The output is a boolean value indicating the success of the subsequence verification. Ensure your implementation handles edge cases such as empty strings and identical strings correctly.

DSA Pattern Breakdown

"Optimal Grid Path Protocol 7"

medium

WHY DOES IT MATTER?

The two-pointer pattern guarantees that we never revisit characters, ensuring linear time. It also eliminates the need for auxiliary data structures like hash maps or dynamic programming tables, keeping space usage minimal. This is crucial in systems where memory is at a premium or when processing massive streams of data.

OPTIMIZATION CHALLENGE

The key insight is that once a character in the target is matched, it can never be matched again, so we can safely discard all preceding characters in the source. This eliminates the exponential blowup of generating all subsequences and reduces the problem to a single pass.

REAL-WORLD CONNECTION

Think of a log monitoring system that needs to detect a specific sequence of events (the target) within a continuous stream of logs (the source). The two-pointer approach is analogous to a sliding window that only moves forward, making it ideal for real-time anomaly detection in distributed microservices.

When explaining this in an interview, emphasize that the algorithm’s simplicity is its strength: it’s a single loop with a conditional, no recursion, no extra memory. Highlight that this makes it trivially parallelizable for very long sources by partitioning the source and merging partial results.

COMPLEXITY AT A GLANCE

⏱ Time:O(n+m)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem of determining whether one string is a subsequence of another is a classic example of linear-time pattern matching. A subsequence preserves the relative order of characters but allows deletions; thus, we can scan both strings simultaneously with two pointers: one iterating over the source and one over the target. Whenever the characters match, we advance the target pointer; otherwise, we only advance the source pointer. If the target pointer reaches the end, the target is a subsequence. This two-pointer technique runs in O(n+m) time and O(1) space, where n and m are the lengths of source and target, respectively.

Naive approaches often involve generating all possible subsequences of the source or using recursion with backtracking, which leads to exponential time complexity (O(2^n)). Such methods quickly become infeasible for strings of moderate length (e.g., 10^5 characters). The optimal paradigm avoids combinatorial explosion by exploiting the fact that we only need to verify the existence of a single ordering, not enumerate all possibilities. By scanning once through the source and only moving forward in the target when matches occur, we guarantee linear time and constant auxiliary space.

This pattern is not only efficient but also highly cache-friendly: the algorithm accesses each character of the source exactly once, leading to predictable memory access patterns. In practice, this makes the solution suitable for large-scale data streams and real-time systems where latency and memory footprint are critical.

Interview Questions on This Problem

Q1How would you modify the two-pointer algorithm if the source string is extremely long and stored in a distributed file system, while the target string is small and fits in memory?

You would stream the source string in chunks, maintaining the current position in the target. For each chunk, iterate through its characters, advancing the target pointer when a match occurs. Since the target is small, you can keep it entirely in memory, and you only need to read the source sequentially, which is efficient in a distributed setting.

Q2A fintech platform needs to verify that a transaction code is a subsequence of a user’s activity log. What edge cases should you consider to avoid false positives?

Consider empty strings (empty target is always a subsequence), case sensitivity (normalize if required), and repeated characters. Also ensure that the algorithm correctly handles Unicode grapheme clusters if the logs contain emojis or non-ASCII characters.

Q3During a high-growth startup interview, you’re asked to explain the time complexity of the subsequence check. How would you justify O(n+m) to a non-technical interviewer?

I would say that we look at each character in the source once and each character in the target once, so the total number of steps is roughly the sum of their lengths. This means the time grows linearly with the size of the input, which is very fast even for large strings.

Examples

Example 1

Input

source = "abcde", target = "ace"

Output

true

Explanation: Initialize pointer `j` at 0 for `target`. Iterate through `source`: 'a' matches `target[0]`, increment `j` to 1. 'b' and 'c' do not match `target[1]` ('c') until 'c' is found, increment `j` to 2. 'd' does not match `target[2]` ('e'). 'e' matches `target[2]`, increment `j` to 3. Since `j` equals the length of `target` (3), return true.

Example 2

Input

source = "abc", target = "axc"

Output

false

Explanation: Initialize pointer `j` at 0. 'a' matches `target[0]`, increment `j` to 1. 'b' does not match `target[1]` ('x'). 'c' does not match `target[1]` ('x'). End of `source` reached, but `j` (1) is less than the length of `target` (3). Return false.

Example 3

Input

source = "", target = ""

Output

true

Explanation: Both strings are empty. The pointer `j` starts at 0 and the length of `target` is 0. Since `j` equals the length of `target`, the condition is satisfied immediately. Return true.

Example 4

Input

source = "ababab", target = "baba"

Output

true

Explanation: Initialize `j` at 0. 'a' does not match `target[0]` ('b'). 'b' matches `target[0]`, increment `j` to 1. 'a' matches `target[1]`, increment `j` to 2. 'b' matches `target[2]`, increment `j` to 3. 'a' matches `target[3]`, increment `j` to 4. `j` equals the length of `target` (4). Return true.

Constraints

1 <= source.length <= 10^5
0 <= target.length <= 10^5
source and target consist of lowercase English letters only.
The total number of test cases is up to 10^4.

Optimal Approach & Strategy

The optimal solution uses two pointers to scan the source and target once, advancing the target pointer only on matches. This yields linear time and constant space.

Brute Force Approach

A naive method would generate all possible subsequences of the source string and check if the target is among them. This requires exponential time and memory, making it impractical for long strings.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n+m)

/**
 * @param {string} source
 * @param {string} target
 * @return {boolean}
 */
var isSubsequence = function(source, target) {
    let j = 0;
    for (let i = 0; i < source.length && j < target.length; i++) {
        if (source[i] === target[j]) {
            j++;
        }
    }
    return j === target.length;
};

class Solution {
public:
    bool isSubsequence(string source, string target) {
        int j = 0;
        for (int i = 0; i < source.size() && j < target.size(); ++i) {
            if (source[i] == target[j]) {
                ++j;
            }
        }
        return j == target.size();
    }
};

class Solution {
    public boolean isSubsequence(String source, String target) {
        int j = 0;
        for (int i = 0; i < source.length() && j < target.length(); i++) {
            if (source.charAt(i) == target.charAt(j)) {
                j++;
            }
        }
        return j == target.length();
    }
}

class Solution:
    def isSubsequence(self, source: str, target: str) -> bool:
        j = 0
        for i in range(len(source)):
            if j < len(target) and source[i] == target[j]:
                j += 1
        return j == len(target)

/**
 * @param {string} source
 * @param {string} target
 * @return {boolean}
 */
var isSubsequence = function(source, target) {
    let j = 0;
    for (let i = 0; i < source.length && j < target.length; i++) {
        if (source[i] === target[j]) {
            j++;
        }
    }
    return j === target.length;
};

Asked in Top Tech Interviews

FlipkartOracle

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Optimal Grid Path Protocol 7 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Optimal Grid Path Protocol 7 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor