Check if Given String Subsequence of Another String in Java

June 22, 2022

Check if Given String Subsequence of Another String in Java

Write a Java program to check if given String is subsequence of another string is asked quite often in Java interviews.

If you have two strings str1 and str2 then str1 is a subsequence of str2 if all the characters in str1 are found in str2, characters may not be found consecutively but characters should be in order.

For example– If str1 = "code" and str2="cportde" then str1 is a subsequence of str2 as you can get all the characters of str1 in str2 in the same order by deleting some of the characters in str2.

If str1="abc" and str2="bsdafgc" then str1 is not the subsequence of str2, as all the characters of str1 are present in str2 but order is different.

Java program to check if string subsequence of another string

To check if string str1 is a subsequence of str2, start from the first character of str1 and iterate the string str2 to check if that character is found.

If yes then move to next character for str1 and check that in str2.

If no then check for the same character of str1 in str2.

There are both recursive and iterative Java programs for checking if the String is subsequence of another string. In this post we’ll see both of the ways.

Iterative Java program to check if String is subsequence of another string

public class SubSequenceChecker {
  public static void main(String[] args) {
    String str1 = "code";
    String str2 = "cportde";
    boolean subSeqFlag = isSubSequenceFound(str1, str2);
    displayResult(str1, str2, subSeqFlag);
    
    str1 = "abc";
    str2 = "bsdafgc";
    subSeqFlag = isSubSequenceFound(str1, str2);
    displayResult(str1, str2, subSeqFlag);
    
    str1 = "knpcode";
    str2 = "isknoppconode";
    subSeqFlag = isSubSequenceFound(str1, str2);
    displayResult(str1, str2, subSeqFlag);

  }
	
  private static boolean isSubSequenceFound(String str1, String str2){
    int j = 0;
    for(int i = 0; i < str2.length(); i++){
      // If char found move to next char
      if(str1.charAt(j) == str2.charAt(i)){
        ++j;
      }
      // Equal means all the characters of str1 are
      // found in str2 in order
      if(j == str1.length()){
        return true;
      }
    }
    return false;
  }
	
  private static void displayResult(String str1, String str2, boolean flag) {
    if(flag)
      System.out.println(str1 + " is a subsequence of " + str2);
    else
      System.out.println(str1 + " is not a subsequence of " + str2);
  }
}

Output

code is a subsequence of cportde
abc is not a subsequence of bsdafgc
knpcode is a subsequence of isknoppconode

Recursive Java program to check if String is subsequence of another string

public class SubSequenceChecker {
  public static void main(String[] args) {
    String str1 = "code";
    String str2 = "cportde";
    boolean subSeqFlag = isSubSequenceFound(str1, str2, 0, 0);
    displayResult(str1, str2, subSeqFlag);

    str1 = "abc";
    str2 = "bsdafgc";
    subSeqFlag = isSubSequenceFound(str1, str2, 0, 0);
    displayResult(str1, str2, subSeqFlag);

    str1 = "knpcode";
    str2 = "isknoppconode";
    subSeqFlag = isSubSequenceFound(str1, str2, 0, 0);
    displayResult(str1, str2, subSeqFlag);
  }
	
  /**
   * Checking if str1 is a subsequence of str2 
  */
  private static boolean isSubSequenceFound(String str1, String str2, int str1Index, int str2Index){
    // exit condition-1 
    // All the chars in str1 are found
    if(str1.length() == str1Index) {
      return true;
    }
    // exit condition-2
    // Str2 is completely iterated without finding all the
    // chars in str1
    if(str2.length() == str2Index) {
      return false;
    }
    // if char is found move both strings by one char
    // otherwise only move str2 by one char
    if(str1.charAt(str1Index) == str2.charAt(str2Index)){
      return isSubSequenceFound(str1, str2, ++str1Index, ++str2Index);
    }else{
      return isSubSequenceFound(str1, str2, str1Index, ++str2Index);
    }
  }

  private static void displayResult(String str1, String str2, boolean flag) {
    if(flag)
      System.out.println(str1 + " is a subsequence of " + str2);
    else
      System.out.println(str1 + " is not a subsequence of " + str2);
  }
}

Output

code is a subsequence of cportde
abc is not a subsequence of bsdafgc
knpcode is a subsequence of isknoppconode

That's all for the topic Check if Given String Subsequence of Another String in Java. If something is missing or you have something to share about the topic please write a comment.

You may also like

KnpCode

June 22, 2022