$show=/label

Java - Check If String is Subsequence of Other String

SHARE:

A quick guide to check if the string is a subsequence of another string in java.

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.

Java - Check If String is Subsequence of Other String


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.



COMMENTS

BLOGGER

About Us

Author: Venkatesh - I love to learn and share the technical stuff.
Name

accumulo,1,ActiveMQ,2,Adsense,1,API,37,ArrayList,18,Arrays,21,Bean Creation,3,Bean Scopes,1,BiConsumer,1,Blogger Tips,1,Books,1,C Programming,1,Collection,8,Collections,32,Collector,1,Command Line,1,Compile Errors,1,Configurations,7,Constants,1,Control Statements,8,Conversions,6,Core Java,135,Corona India,1,Create,2,CSS,1,Date,3,Date Time API,38,Dictionary,1,Difference,2,Download,1,Eclipse,3,Efficiently,1,Error,1,Errors,1,Exceptions,7,Fast,1,Files,17,Float,1,Font,1,Form,1,Freshers,1,Function,3,Functional Interface,2,Garbage Collector,1,Generics,4,Git,9,Grant,1,Grep,1,HashMap,2,HomeBrew,2,HTML,2,HttpClient,2,Immutable,1,Installation,1,Interview Questions,6,Iterate,2,Jackson API,3,Java,32,Java 10,1,Java 11,6,Java 12,5,Java 13,2,Java 14,2,Java 8,127,Java 8 Difference,2,Java 8 Stream Conversions,4,java 8 Stream Examples,12,Java 9,1,Java Conversions,14,Java Design Patterns,1,Java Files,1,Java Program,3,Java Programs,113,Java Spark,1,java.lang,4,java.util. function,1,JavaScript,1,jQuery,1,Kotlin,11,Kotlin Conversions,6,Kotlin Programs,10,Lambda,2,lang,29,Leap Year,1,live updates,1,LocalDate,1,Logging,1,Mac OS,3,Math,1,Matrix,6,Maven,1,Method References,1,Mockito,1,MongoDB,3,New Features,1,Operations,1,Optional,6,Oracle,5,Oracle 18C,1,Partition,1,Patterns,1,Programs,1,Property,1,Python,2,Quarkus,1,Read,1,Real Time,1,Recursion,2,Remove,2,Rest API,1,Schedules,1,Serialization,1,Servlet,2,Sort,1,Sorting Techniques,8,Spring,2,Spring Boot,23,Spring Email,1,Spring MVC,1,Streams,29,String,61,String Programs,28,String Revese,1,Swing,1,System,1,Tags,1,Threads,11,Tomcat,1,Tomcat 8,1,Troubleshoot,24,Unix,3,Updates,3,util,5,While Loop,1,
ltr
item
JavaProgramTo.com: Java - Check If String is Subsequence of Other String
Java - Check If String is Subsequence of Other String
A quick guide to check if the string is a subsequence of another string in java.
https://1.bp.blogspot.com/-Yik9QP7WobE/YY50wYFCOEI/AAAAAAAADcw/_RdazsbdIO8sE-_sLcixVGu9cimN4_HMwCLcBGAsYHQ/w400-h297/Java%2B-%2BCheck%2BIf%2BString%2Bis%2BSubsequence%2Bof%2BOther%2BString.png
https://1.bp.blogspot.com/-Yik9QP7WobE/YY50wYFCOEI/AAAAAAAADcw/_RdazsbdIO8sE-_sLcixVGu9cimN4_HMwCLcBGAsYHQ/s72-w400-c-h297/Java%2B-%2BCheck%2BIf%2BString%2Bis%2BSubsequence%2Bof%2BOther%2BString.png
JavaProgramTo.com
https://www.javaprogramto.com/2021/11/java-check-string-subsequence.html
https://www.javaprogramto.com/
https://www.javaprogramto.com/
https://www.javaprogramto.com/2021/11/java-check-string-subsequence.html
true
3124782013468838591
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content