Java - Check If String is Subsequence of Other String

1. Overview

In this tutorial, we'll learn how to check whether the string is subsequence of another String in java.

This problem can be solved using iteration and recursive approach.

2 Whart is subsequence?

when zero or more characters are removed from in the input string then it is a valid subsequence. Here the the order is important.

if you understand this concept then you solve the problem easily. Remember suubsequcen go in the single direction, no backward direction.

Example String ABC

sub sequences are "", A, B, C, AB, AC, BC, ABC

"" is when all characters are removd

A, B, C are when two characters are removed.

AB, AC, BC when one character is removed

ABC when zero characters are removed.

CA, BA, CBA are not subsequences because these are not in the order of the string. CA -> after C there is no A in the input string, BA -> after B there is no A character input string.

Example 1:

String: "ABCDE"

Subsequence: "ACE"

Output: true

subsequence ACE is present in the string "ABCDE". ACE is present in the same order in the input string.

Example 2:

String: "ABCDE"

Subsequence: "AEC"

Output: false

AEC is not a subsequence because AE is a continuous sequence but C is not in the sequence in the input string. C is in between in the A and E in the input string.

3. Java - Check If String is Subsequence of Other String Using Iterative Approach

Observe the below alogirithm to solve this problem in O(n) time.

Input or other String: "ABCDE"

Subsequence: "ACE"

First take first characters from both strings and compare them. If two characters are equals then go for the next characters comparison from the both strings. If not then take the next character from the other string and compare it with the 1st character of the subsequence string.

Repeat this process until we reach the other string end. By end of this process, if all subsequences characters are matched then it is a valid subsequences.

if there are some characters left and not matched with the other string then it is not a valid subsequence.

Other String: ABCDE

subsequence: ACE

A) Take the first characters from both strings and compare them.

    A == A

    Both are same. Move the comparisons for the next characters.

B) Next, take second character from other string and subsequcne string.

    B == C

    No match. 

C) Now take the next character from the other string and compare with the C character from the subsequence current unmatched character.

    

    Next character from other string : C

    Curent unmatched character from subsequence string: C

    C == C

    Both are matched.

D) Now take the next character from both strings.

    Next character from other string : D

    Curent unmatched character from subsequence string: E

    D == E 

    No match

E) Now take the next character from the other string and compare with the E character from the subsequence current unmatched character.

    

    Next character from other string : E

    Curent unmatched character from subsequence string: E

    E == E

    Both are matched and no characters are left on the other string and there are no other characters.

And also there are no characters from the subsequence also. All characters are matched with other string.

So ACE is a valid subsequence of ABCDE.

If the subsequence is AEC then by end of comparisons of all characters from the other string with subsequcne, A character C is left from the subsequence string. Hence, AEC is not a valid subsequcne of ABCDE.

Look at the below code.

package com.javaprogramto.programs.strings;

public class StrintSubSequnceIterativeExample {

	public static void main(String[] args) {

		String otherString = "ABCDE";
		String subsequence = "ACE";

		boolean isValidSubsequence = checkSubsequence(otherString, subsequence);

		System.out.println(isValidSubsequence);

		otherString = "ABCDE";
		subsequence = "AEC";

		isValidSubsequence = checkSubsequence(otherString, subsequence);

		System.out.println(isValidSubsequence);

	}

	private static boolean checkSubsequence(String otherString, String subsequence) {

		// if the subsequence length is greather than subsequence, then inputs are not
		// valid and not subsequence.
		if (otherString.length() < subsequence.length()) {
			return false;
		}

		int subsequenceIndex = 0;
		for (int otherStringIndex = 0; otherStringIndex < otherString.length(); otherStringIndex++) {
			// whether there is a match or not with other string. we will increment other
			// string index by 1 always.

			if (otherString.charAt(otherStringIndex) == subsequence.charAt(subsequenceIndex)) {
				// if both characters are matching then incrementing the index of subsequence
				// string.
				subsequenceIndex++;
			}

		}

		// always subsequence length and sub sequence index should be same for a valid
		// sub sequence.
		return subsequence.length() == subsequenceIndex;
	}

}

Output:

true
false

In this program, we have passed two inputs with valid and invalid subsequences for the better understanding.

Time complexity: O(n)

Auxilary space complexity: O(1)

4. Java - Check If String is Subsequence of Other String Using Recursive Approach

Recursive approach is not suitable for this problem because iterative approach is best solution with no auxilary space.

If you use recustive way, then it uses the additional stacks recursive calls.

In the below code, we compare the character from the last index from both strings and go back to till the zero index.

And also we need to pass the current indexes to the recursive method.

Look at the below approach.

package com.javaprogramto.programs.strings.subsequence;

public class StrintSubSequnceRecursiveExample {

	public static void main(String[] args) {

		String otherString = "ABCDE";
		String subsequence = "ACE";

		boolean isValidSubsequence = checkSubsequence(otherString, subsequence, otherString.length(),
				subsequence.length());

		System.out.println(isValidSubsequence);

		otherString = "ABCDE";
		subsequence = "AEC";

		isValidSubsequence = checkSubsequence(otherString, subsequence, otherString.length(), subsequence.length());

		System.out.println(isValidSubsequence);

	}

	private static boolean checkSubsequence(String otherString, String subsequence, int otherLength, int subLength) {

		// if at any point if the sub sequence length becomes zero mean all character of
		// sub sequence are matched
		// or if other is reached 0 index and sub sequences also reached 0 index at the
		// same time then it is a valid sub sequence. so because of this we are first
		// checking the sub sequence length 0
		if (subLength == 0) {
			return true;
		}

		if (otherLength == 0) {
			return false;
		}

		// comparing the last characters first and then going backward for the previous
		// letters comparison.
		if (otherString.charAt(otherLength - 1) == subsequence.charAt(subLength - 1)) {
			// if matched then decrement the legth for the both strings.
			return checkSubsequence(otherString, subsequence, otherLength - 1, subLength - 1);
		} else {
			// if no match then decrement only for the other string. because sub sequence
			// current character is not matched yet
			return checkSubsequence(otherString, subsequence, otherLength - 1, subLength);
		}
	}

}

This program also produces the same output.

Time complexity: O(n)

Auxilary space complexity: O(n)

5. Conclusion

In this article, we have seen how to check string is sub sequence of another string in java using iterative and recursive approaches.

GitHub

How to check two strings are anagrams or not?