Check if One String Is a Subsequence of Another (Java)

Check if One String Is a Subsequence of Another (Java)

In this post, we will learn how to check whether one string is a subsequence of another string using Java. We will solve the problem using both iterative and recursive approaches and test it with multiple input cases.

---

What is a Subsequence?

A string s2 is a subsequence of string s1 if all characters of s2 appear in s1 in the same order, but not necessarily contiguously.

Examples:

ABCDEF & ADE   → Subsequence
ABCDEF & AEF   → Subsequence
ABCDEF & AED   → Not a Subsequence

---

Approaches Used

• Iterative Approach: Two Pointer Technique
• Recursive Approach: Compare last characters

---

Java Code Implementation

public class SubsequenceCheck {

    public static void main(String[] args) {

        String[][] testCases = {
            {"ABCDEF", "ADE"},
            {"ABCDEF", "AEF"},
            {"ABCDEF", "AED"},
            {"HELLO", "HLO"},
            {"HELLO", "OLL"}
        };

        for (String[] pair : testCases) {
            String s1 = pair[0];
            String s2 = pair[1];

            System.out.println("Main String: " + s1);
            System.out.println("Subsequence: " + s2);
            System.out.println("Iterative Check: " + isSubsequenceIterative(s1, s2));
            System.out.println("Recursive Check: " +
                    isSubsequenceRecursive(s1, s2, s1.length(), s2.length()));
            System.out.println();
        }
    }

    // Iterative approach using two pointers
    private static boolean isSubsequenceIterative(String s1, String s2) {

        int j = 0;

        for (int i = 0; i < s1.length() && j < s2.length(); i++) {
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
        }
        return j == s2.length();
    }

    // Recursive approach
    private static boolean isSubsequenceRecursive(String s1, String s2, int n, int m) {

        if (m == 0)
            return true;

        if (n == 0)
            return false;

        if (s1.charAt(n - 1) == s2.charAt(m - 1))
            return isSubsequenceRecursive(s1, s2, n - 1, m - 1);
        else
            return isSubsequenceRecursive(s1, s2, n - 1, m);
    }
}

---

Explanation

1. Iterative Approach (Two Pointer Technique)

• Initialize two pointers for both strings
• Traverse the main string character by character
• Move the second pointer only when characters match
• If all characters of second string are matched, it is a subsequence

Technique Used: Two Pointer Technique

---

2. Recursive Approach

• If the second string becomes empty, return true
• If the first string becomes empty first, return false
• Compare last characters and reduce the problem size

Technique Used: Recursion

---

Sample Output

Main String: ABCDEF
Subsequence: ADE
Iterative Check: true
Recursive Check: true

Main String: ABCDEF
Subsequence: AED
Iterative Check: false
Recursive Check: false

---

Time & Space Complexity

Approach	Time Complexity	Space Complexity
Iterative	O(n)	O(1)
Recursive	O(n)	O(n) (Recursion Stack)

---

Interview Tip

In interviews, the iterative two pointer approach is preferred because it avoids recursion overhead and uses constant extra space.

---

Want to Go Further?

To deepen your understanding, try solving these variations:

• Check subsequence in a case-insensitive manner
• Count how many times a subsequence appears
• Longest Common Subsequence (LCS)

👉 Tip: This problem is a foundation for many advanced DP problems.

---

Category: Strings
Difficulty: Easy
Technique: Two Pointers, Recursion