Is Subsequence - Java Solution

1. Introduction

In this blog post, we'll tackle a common problem in string manipulation: checking if one string is a subsequence of another. This problem is fundamental in understanding how to navigate and compare strings in various programming scenarios, including algorithm design, pattern matching, and data processing.

Problem

The challenge is to determine whether a given string 's' is a subsequence of another string 't'. A string is considered a subsequence of another if it can be derived by deleting some (or no) characters from the other string without changing the order of the remaining characters.

2. Solution Steps

1. Initialize pointers for both strings 's' and 't'.

2. Traverse through string 't' while comparing it with 's'.

3. If a character in 's' matches with a character in 't', move the pointer of 's'.

4. Check if we have traversed the entire length of 's'.

3. Code Program

public class IsSubsequence {
    public static void main(String[] args) {
        System.out.println(isSubsequence("ace", "abcde")); // Example 1
        System.out.println(isSubsequence("aec", "abcde")); // Example 2
    }

    // Function to check if 's' is a subsequence of 't'
    public static boolean isSubsequence(String s, String t) {
        int indexS = 0; // Pointer for string 's'
        int indexT = 0; // Pointer for string 't'

        while (indexT < t.length()) {
            if (indexS < s.length() && s.charAt(indexS) == t.charAt(indexT)) {
                indexS++; // Move pointer in 's' if there's a match
            }
            indexT++; // Always move pointer in 't'
        }
        return indexS == s.length(); // Check if all characters in 's' were matched
    }
}

Output:

true
false

Explanation:

1. isSubsequence: This function iterates through the characters of string 't' using the indexT pointer. It checks each character against the current character in 's' (pointed by indexS).

2. If a character in 's' matches with a character in 't', we move the indexS pointer forward.

3. The loop continues until we have gone through all characters in 't'.

4. The function returns true if indexS equals the length of 's', indicating all characters in 's' were found in 't' in order.