Check if One String Is a Subsequence of Another String in Java — Definition, Examples and Program

Check if One String Is a Subsequence of Another String in Java

A string is said to be a subsequence of another string if all its characters appear in the same order, but not necessarily consecutively.

This problem is commonly asked in interviews and is an excellent example of efficient string traversal using pointers.

Understanding Subsequence

For a string sub to be a subsequence of main:

• All characters of sub must appear in main.
• The order of characters must remain the same.
• Characters do not need to be contiguous.

Example 1

Main String: programming

Subsequence: pgm

Output: Yes, it is a subsequence

Example 2

Main String: coding

Subsequence: cdg

Output: Yes, it is a subsequence

Example 3

Main String: hello

Subsequence: hol

Output: No, it is NOT a subsequence

Logic Explanation (Two Pointer Approach)

1. Initialize two pointers, one for each string.
2. Compare characters at both pointers.
3. If characters match, move both pointers forward.
4. If not, move only the main string pointer.
5. If all characters of subsequence are matched, return true.

Java Program to Check Subsequence

import java.util.Scanner;

public class SubsequenceCheck {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.print("Enter main string: ");
        String main = sc.nextLine();

        System.out.print("Enter subsequence string: ");
        String sub = sc.nextLine();

        int i = 0, j = 0;

        while (i < main.length() && j < sub.length()) {

            if (main.charAt(i) == sub.charAt(j)) {
                j++;
            }
            i++;
        }

        if (j == sub.length()) {
            System.out.println("Yes, it is a subsequence");
        } else {
            System.out.println("No, it is NOT a subsequence");
        }
    }
}

Sample Output

Enter main string: programming
Enter subsequence string: pgm
Yes, it is a subsequence

Important Notes

• An empty string is always a subsequence.
• Time complexity is O(n).
• No extra space is used.

Practice Challenges

1. Check subsequence ignoring case sensitivity.
2. Count how many times a subsequence appears.
3. Check subsequence using recursion.

Subsequence problems are foundational for dynamic programming and competitive programming. Mastering this logic is essential.