How to Check if a String Contains a Second String with its Characters in Order?

Question

I'm just starting out and I'm completely lost on how to do this.

I want to be able to check a string for a smaller string and return true if the string contains the letters of the string in order.

I'm not sure how to go about making sure the letters of the second string are in order, even if there are other letters between them.

An example would be that "chemistry" would return true for the string "hit".

It would return false for the string "him" though.

Any help would be greatly appreciated.

EDIT: Thank you, I changed the word "substring" to string. As I said, I'm just beginning and wasn't aware that meant something else. I really appreciate all the help. It should get me moving in the right direction.

Answer 1

The general approach is to iterate over the characters of the longer string ("chemistry"), always keeping track of the index of the next required character from the shorter string ("hit" — first 0, then 1 once you find h, then 2 once you find i, and then when you find t you're done). For example:

public static boolean containsSubsequence(
        final String sequence, final String subsequence) {
    if (subsequence.isEmpty()) {
        return true;
    }
    int subsequenceIndex = 0;
    for (int i = 0; i < sequence.length(); ++i) {
        if (sequence.charAt(i) == subsequence.charAt(subsequenceIndex)) {
            ++subsequenceIndex;
            if (subsequenceIndex == subsequence.length()) {
                return true;
            }
        }
    }
    return false;
}