Is Subsequence

Problem

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1: s = "abc", t = "ahbgdc"

Return true.

Example 2: s = "axc", t = "ahbgdc"

Return false.

Solution

public class Solution {
    public boolean isSubsequence(String s, String t) {
        int sIndex = 0, tIndex = 0;
        int sLen = s.length(), tLen = t.length();
        while (sIndex < sLen && tIndex < tLen) {
            if (s.charAt(sIndex) == t.charAt(tIndex++)) sIndex++;
        }
        return sIndex == sLen;
    }
}

Analysis

A typical solution to determine subsequence using Two Pointers
We loop through the bigger string and check if smaller string has same char in bigger string
If so, we increment the index of smaller string
At the end, we simply return whether the index is equal to the length of smaller string
Notice that subsequence is defined as removing some (can be 0) characters from given input, it does not have to be consecutive