Given two strings, determine if the second string is a subsequence of the first string. Explain the time and space complexity of your solution.

Let's talk about strings. Suppose you're given two strings, text and pattern. Your task is to implement a function that efficiently determines if the pattern is a subsequence of the text. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, "ace" is a subsequence of "abcde", but "aec" is not.

Your function should return true if the pattern is a subsequence of the text, and false otherwise.

Example 1:

text = "abcde" pattern = "ace"

Output: true

Example 2:

text = "abcde" pattern = "aec"

Output: false

Example 3:

text = "abcde" pattern = ""

Output: true (An empty string is always a subsequence)

Example 4:

text = "" pattern = "abc"

Output: false (A non-empty string cannot be a subsequence of an empty string)

Consider edge cases such as empty strings and differing lengths. Discuss the time and space complexity of your solution. Aim for an optimal solution.

Let's explore how to determine if a string pattern is a subsequence of another string text.

Problem Description

Given two strings, text and pattern, we want to check if pattern is a subsequence of text. A subsequence can be formed by deleting some characters from text without changing the order of the remaining characters.

Naive Approach

A simple, brute-force approach would be to generate all possible subsequences of text and then check if pattern is among them. However, this is highly inefficient because the number of subsequences can be exponential in the length of text.

Optimal Solution

A more efficient approach involves using two pointers, one for text and one for pattern. We iterate through text, and whenever we find a character that matches the current character in pattern, we advance the pattern pointer. If we reach the end of pattern, it means pattern is a subsequence of text.

Here's an implementation in Python:

def is_subsequence(text: str, pattern: str) -> bool:
    i = 0  # pointer for text
    j = 0  # pointer for pattern
    
    while i < len(text) and j < len(pattern):
        if text[i] == pattern[j]:
            j += 1
        i += 1
    
    return j == len(pattern)

# Example usage
text1 = "abcde"
pattern1 = "ace"
print(f'{pattern1} is a subsequence of {text1}: {is_subsequence(text1, pattern1)}')

text2 = "abcde"
pattern2 = "aec"
print(f'{pattern2} is a subsequence of {text2}: {is_subsequence(text2, pattern2)}')

text3 = "abcde"
pattern3 = ""
print(f'"{pattern3}" (empty string) is a subsequence of {text3}: {is_subsequence(text3, pattern3)}')

text4 = ""
pattern4 = "abc"
print(f'{pattern4} is a subsequence of "" (empty string): {is_subsequence(text4, pattern4)}')

class Solution {
    public boolean isSubsequence(String text, String pattern) {
        int i = 0; // pointer for text
        int j = 0; // pointer for pattern

        while (i < text.length() && j < pattern.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            i++;
        }

        return j == pattern.length();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        String text1 = "abcde";
        String pattern1 = "ace";
        System.out.println(pattern1 + " is a subsequence of " + text1 + ": " + solution.isSubsequence(text1, pattern1));

        String text2 = "abcde";
        String pattern2 = "aec";
        System.out.println(pattern2 + " is a subsequence of " + text2 + ": " + solution.isSubsequence(text2, pattern2));

        String text3 = "abcde";
        String pattern3 = "";
        System.out.println("\"" + pattern3 + "\" (empty string) is a subsequence of " + text3 + ": " + solution.isSubsequence(text3, pattern3));

        String text4 = "";
        String pattern4 = "abc";
        System.out.println(pattern4 + " is a subsequence of \"\" (empty string): " + solution.isSubsequence(text4, pattern4));
    }
}

Time Complexity Analysis

The time complexity of this optimal solution is O(N), where N is the length of the text string. This is because we iterate through the text string at most once.

Space Complexity Analysis

The space complexity is O(1) because we only use a constant amount of extra space for the pointers i and j, regardless of the input string sizes.

Edge Cases

1. Empty Pattern: If pattern is an empty string, it's always a subsequence of any string text. The algorithm correctly handles this because the loop condition j < len(pattern) will be false from the start, and the function will return true.
2. Empty Text: If text is an empty string and pattern is not, then pattern cannot be a subsequence of text. The algorithm correctly handles this, as the loop will terminate immediately, and j will not equal the length of pattern, resulting in a false return.
3. Identical Strings: If text and pattern are identical, pattern is a subsequence of text. The algorithm correctly handles this case because each character in text will match the corresponding character in pattern, and j will reach the end of pattern.
4. Pattern Longer than Text: If pattern is longer than text, pattern cannot be a subsequence of text. The algorithm handles this correctly because even if the initial characters match, i will reach the end of text before j reaches the end of pattern.