If Given String Sub-Sequence of Another String in Java

I recently remembered one interview 6-7 years back where I was asked to write a Java program to find if given string is the subsequence of another string. I started writing the program but my approach was wrong as I was getting confused between subsequence and substring.

What I wrote was to ensure that given string is the substring of another string as my assumption was that the characters should come continuously. As example if I have to find "net" exists in "netjs", then it is true as all the characters n, e, t are coming continuously in netjs.

But that’s not what subsequence means so before writing the program to ensure that given string is the subsequence of another string first let’s have a proper definition of what subsequence means.

What is a subsequence

A subsequence is a sequence where all the characters of the subsequence are present in another sequence, are in order but may not be continuous. As example – If our subsequence is “net” and we have to find if that subsequence exists in the string “npeght” then it should return true as all the characters of the subsequence (n, e, t) are present in the given string and characters are in the same order. If we delete the extra elements in the second string (p, g, h) then we get the same string.

Approach for the Java program

We can have both iterative and recursive logic for the program to find if given string is the subsequence of another string. Approach remains same for both if we have to find that String-1 is subsequence of String-2 then we start from one end of the string, it can be leftmost or rightmost (In the program here I started from the leftmost character of the strings). If character of String-1 is found in String-2 then we increment the index by 1 for both strings, if character of String-1 is not found in String-2 then we increment the index by 1 only for String-2.

Java program to find if given string is the subsequence of another string

This code has both iterative and recursive solutions.

Method isStringSequenceFound(String str1, String str2, int i, int j)is for recursive solution.
Method isStringSequenceFound(String str1, String str2) is for iterative solution.

public class SubSequenceFinder {

  public static void main(String[] args) {
    // Iterative method call
    String str1 = "abc";
    String str2 = "asc";
    boolean flag = isStringSequenceFound(str1, str2);
    System.out.println(str1 + " is subsequence of " + str2 + " - " + flag);
    
    // Recursive method call
    str1 = "java";
    str2 = "javelina";
    flag = isStringSequenceFound(str1, str2, 0, 0);
    System.out.println(str1 + " is subsequence of " + str2 + " - " + flag);
    
    // Iterative method call
    str1 = "abc";
    str2 = "asbbdfc";
    flag = isStringSequenceFound(str1, str2);
    System.out.println(str1 + " is subsequence of " + str2 + " - " + flag);
  }
 
  // Recursive method to find sub-sequence
  static boolean isStringSequenceFound(String str1, String str2, int i, int j){
    // Exit condition - if i becomes equal to length 
    // of string-1 that means all the characters are found in the second string
    if(str1.length() == i){
      return true;
    }
    //if length of String-2 becomes equal to j that means string 2 is completely
    // traversed and all the characters of string-1 are not found
    if(str2.length() == j){
      System.out.println();
      return false;
    }
    //
    if(str1.charAt(i) == str2.charAt(j)){
      // increase both i and j by 1, if char is found
      return isStringSequenceFound(str1, str2, ++i, ++j);
    }else{
      return isStringSequenceFound(str1, str2, i, ++j);
    }
  }
 
  // iterative method to find sub-sequence
  static boolean isStringSequenceFound(String str1, String str2){
    int j = 0;
    for(int i = 0; i < str2.length(); i++){
      if(str1.charAt(j) == str2.charAt(i)){
        ++j;
      }
      // All the characters of String-1 are found in String-2
      if(j == str1.length()){
        return true;
      }
    }
    // If it comes here that means all the characters of String-1
    // are not found in string-2
    return false;
  }
}

Output

abc is subsequence of asc - false
java is subsequence of javelina - true
abc is subsequence of asbbdfc - true

That's all for this topic If Given String Sub-Sequence of Another String in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Wednesday, May 12, 2021